Pre-Triangulations and Liftable Complexes
Tóm tắt
We introduce the concept of pre-triangulations, a relaxation of triangulations that goes beyond the frequently used concept of pseudo-triangulations. Pre-triangulations turn out to be more natural than pseudo-triangulations in certain cases. We show that pre-triangulations arise in three different contexts: In the characterization of polygonal complexes that are liftable to three-space in a strong sense, in flip sequences for general polygonal complexes, and as graphs of maximal locally convex functions.
Tài liệu tham khảo
Aichholzer, O., Aurenhammer, F., Krasser, H., Brass, P.: Pseudo-triangulations from surfaces and a novel type of edge flip. SIAM J. Comput. 32, 1621–1653 (2003)
Aurenhammer, F.: Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Comput. Surv. 23, 345–405 (1991)
Aurenhammer, F.: A criterion for the affine equivalence of cell complexes in R d and convex polyhedra in R d+1. Discrete Comput. Geom. 2, 49–64 (1987)
Aurenhammer, F., Hackl, T., Krasser, H.: Short flip sequences for constructing the Delaunay triangulation. Manuscript (2006)
Aurenhammer, F., Krasser, H.: Pseudo-simplicial complexes from maximal locally convex functions. Discrete Comput. Geom. 35, 201–221 (2006)
Bern, M., Eppstein, D.: Mesh generation and optimal triangulation. In: Du, D.-Z., Hwang, F. (eds.) Computing in Euclidean Geometry. Lecture Notes Series on Computing, vol. 4, pp. 47–123. World Scientific, Singapore (1995)
Brøndsted, A.: An Introduction to Convex Polytopes. Springer, Berlin (1983)
Crapo, H., Whiteley, W.: Plane self stresses and projected polyhedra. Struct. Topol. 20, 55–78 (1993)
Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, Berlin (1987)
Edelsbrunner, H., Shah, N.R.: Incremental topological flipping works for regular triangulations. Algorithmica 15, 223–241 (1996)
Fortune, S.: Voronoi diagrams and Delaunay triangulations. In: Du, D.-Z., Hwang, F. (eds.) Computing in Euclidean Geometry. Lecture Notes Series on Computing, vol. 4, pp. 225–265. World Scientific, Singapore (1995)
Goodman, J.E., Pollack, R.: Multidimensional sorting. SIAM J. Comput. 12, 484–507 (1983)
Grünbaum, B.: Convex Polytopes. Wiley–Interscience, London (1967)
Hackl, T.: Manipulation of pseudo-triangular surfaces. Master thesis, Institute for Theoretical Computer Science, University of Technology, Graz, Austria (2004)
Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations. Discrete Comput. Geom. 22, 333–346 (1999)
Lawson, C.L.: Properties of n-dimensional triangulations. Comput. Aided Geom. Des. 3, 231–246 (1986)
Lee, C.W.: Subdivisions and triangulations of polytopes. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 383–406. CRC Press, Boca Raton (2004)
Lee, D.T., Lin, A.K.: Generalized Delaunay triangulation for planar graphs. Discrete Comput. Geom. 1, 201–217 (1986)
Orden, D., Santos, F.: The polytope of non-crossing graphs on a planar point set. Discrete Comput. Geom. 33, 275–305 (2005)
Pocchiola, M., Vegter, G.: Topologically sweeping visibility complexes via pseudo-triangulations. Discrete Comput. Geom. 16, 419–453 (1996)
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)
Rote, G., Schulz, A.: A pointed Delaunay pseudo-triangulation of a simple polygon. In: Proceedings of the 21st European Workshop on Computational Geometry, pp. 77–80 (2005)
Steinitz, E.: Polyeder und Raumeinteilungen. Enzyklopaedie der Math. Wiss. III AB 12, Leipzig (1916)
Streinu, I.: A combinatorial approach to planar non-colliding robot arm motion planning. In: Proceedings of the 41st IEEE Symposium on FOCS, pp. 443–453 (2000)