Spatial embedding of pseudo-triangulations

ABSTRACT

We show that pseudo-triangulations have natural embeddings in three-space. As a consequence, various concepts for triangulations, like flipping to optimality, (constrained) Delaunayhood, and a polytope representation carry over to pseudo-triangulations.

REFERENCES

• 1: P. K. Agarwal, J.Basch, L.J.Guibas, J.Hershberger, L.Zhang. Deformable free space tilings for kinetic collision detection. In B.R.Donald, K.Lynch, D.Rus (eds.), Algorithmic and Computational Robotics: New Directions (Proc. 5th Workshop Algorithmic Found. Robotics), 2001, 83--96.
• 2: H. Ahn, S.-W. Cheng, O. Cheong, J.Snoeyink. The reflex-free hull. 13th Canadian Conf. Computational Geometry 2001, 9--12.
• 3: O.Aichholzer, F.Aurenhammer. Straight skeletons for general polygonal figures in the plane. In: Voronoi's Impact on Modern Sciences II, A.M.Samoilenko (ed.), Proc. Institute of Mathematics of the National Academy of Sciences of Ukraine 21, 1998, 7--21.
• 4: Oswin Aichholzer , Franz Aurenhammer , Ferran Hurtado, Sequences of spanning trees and a fixed tree theorem, Computational Geometry: Theory and Applications, v.21 n.1, p.3-20, January 2002 [doi>10.1016/S0925-7721(01)00042-6]
• 5: O.Aichholzer, F.Aurenhammer, H.Krasser. Adapting pseudo-triangulations with a near-linear number of edge flips. Manuscript, 2002.
• 6: O.Aichholzer, F.Aurenhammer, H.Krasser, B.Speckmann. Convexity minimizes pseudo-triangulations. Proc. 14th Canadian Conf. Computational Geometry 2002, 158-161.
• 7: F Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, v.16 n.1, p.78-96, Feb. 1987 [doi>10.1137/0216006]
• 8: F.Aurenhammer. A criterion for the affine equivalence of cell complexes in Rd and convex polyhedra in Rd+1. Discrete & Computational Geometry, 2 (1987), 49--64.
• 9: F. Aurenhammer, A relationship between Gale transforms and Voronoi diagrams, Discrete Applied Mathematics, v.28 n.2, p.83-91, Aug. 1990 [doi>10.1016/0166-218X(90)90108-O]
• 10: F.Aurenhammer, Y.-F.Xu. Optimal triangulations. In: P.M.Pardalos, C.A.Floudas (eds), Encyclopedia of Optimization 4, Kluwer Academic Publishing, 2000, 160--166.
• 11: M.Bern, D.Eppstein. Mesh generation and optimal triangulation. In: D.-Z.Du, F.Hwang (eds), Computing in Euclidean Geometry, Lecture Notes Series on Computing 4, World Scientific, 1995, 47--123.
• 12: L.J.Billera, P.Filliman, B.Sturmfels. Constructions and complexity of secondary polytopes. Advances in Mathematics 83 (1990), 155--179.
• 13: H.Bronnimann, L.Kettner, M.Pocchiola, J.Snoeyink. Counting and enumerating pseudo-triangulations with the greedy flip algorithm. Manuscript, 2001.
• 14: B.Chazelle, H.Edelsbrunner, M.Grigni, L.J.Guibas, J.Hershberger, M.Sharir, J.Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica 12 (1994), 54--68.
• 15: L.P.Chew. Constrained Delaunay triangulations. Algorithmica 4 (1989), 97--108.
• 16: H.Crapo, W.Whiteley. Spaces of stresses, projections, and parallel drawings of spherical polyhedra. Beitrage Algebra Geom. 35 (1994), 259--281.
• 17: H.Edelsbrunner. The union of balls and its dual shape. Discrete & Computational Geometry 13 (1995), 415--440.
• 18: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 19: H.Edelsbrunner, N.R.Shah. Incremental topological flipping works for regular triangulations. Algorithmica 15 (1996), 223--241.
• 20: S.Fortune. Voronoi diagrams and Delaunay triangulations. In: D.-Z.Du, F.Hwang (eds), Computing in Euclidean Geometry, Lecture Notes Series on Computing 4, World Scientific, 1995, 225--265.
• 21: I. M. Gelfand, M. M. Kapranov, A. V. Zelevinsky. Newton polyhedra of principal A-determinants. Soviet Math. Dokl. 308 (1989), 20--23.
• 22: Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations, Journal of Algorithms, v.23 n.1, p.51-73, April 1997 [doi>10.1006/jagm.1995.0797]
• 23: R.Haas, F.Santos, B.Servatius, D.Souvaine, I.Streinu, W.Whiteley. Planar minimally rigid graphs have pseudo-triangular embeddings. Manuscript, 2002.
• 24: Lutz Kettner , David Kirkpatrick , Andrea Mantler , Jack Snoeyink , Bettina Speckmann , Fumihiko Takeuchi, Tight degree bounds for pseudo-triangulations of points, Computational Geometry: Theory and Applications, v.25 n.1-2, p.3-12, May 2003 [doi>10.1016/S0925-7721(02)00126-8]
• 25: D.Kirkpatrick, J.Snoeyink, B.Speckmann. Kinetic collision detection for simple polygons. Intern. J. Computational Geometry & Applications 12 (2002), 3--27.
• 26: David Kirkpatrick , Bettina Speckmann, Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons, Proceedings of the eighteenth annual symposium on Computational geometry, p.179-188, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513423]
• 27: Charles L. Lawson, Properties of n-dimensional triangulations, Computer Aided Geometric Design, v.3 n.4, p.231-246, 1987 [doi>10.1016/0167-8396(86)90001-4]
• 28: C.W.Lee. The associahedron and triangulations of the n -gon. European J. Combinatorics 10 (1989), 173--181.
• 29: D.T.Lee, A.K.Lin. Generalized Delaunay triangulation for planar graphs. Discrete & Computational Geometry 1 (1986), 201--217.
• 30: D.Orden, F.Santos. The polyhedron of non-crossing graphs on a planar point set. Manuscript, 2002.
• 31: Michel Pocchiola , Gert Vegter, Minimal tangent visibility graphs, Computational Geometry: Theory and Applications, v.6 n.5, p.303-314, Sept. 1996 [doi>10.1016/0925-7721(95)00016-X]
• 32: M.Pocchiola, G.Vegter. Topologically sweeping visibility complexes via pseudo-triangulations. Discrete & Computational Geometry 16 (1996), 419--453.
• 33: M.Pocchiola, G.Vegter. On polygon covers. Contemporary Mathematics 223 (1999), 257--258.
• 34: D.Randall, G.Rote, F.Santos, J.Snoeyink. Counting triangulations and pseudo-triangulations of wheels. Proc. 13th Canadian Conf. Computational Geometry 2001, 117--120.
• 35: V.T.Rajan, Optimality of the Delaunay triangulation in Rd. Discrete & Computational Geometry 12 (1994), 189--202.
• 36: G.Rote, F.Santos, I.Streinu. Expansive motions and the polytope of pointed pseudo-triangulations. Manuscript, FU-Berlin, 2001.
• 37: G.Rote, C.A.Wang, L.Wang, Y.Xu. On constrained minimum pseudo-triangulations. Manuscript, FU-Berlin, 2002.
• 38: B.Speckmann, C.D.Toth. Allocating vertex p-guards in simple polygons via pseudo-triangulations. Abstr. 18th Europ. Workshop Computational Geometry, 2002, 12--15.
• 39: I. Streinu, A combinatorial approach to planar non-colliding robot arm motion planning, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.443, November 12-14, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
constrained regular complexes, polytope representation, pseudo-triangulations, three-dimensional embedding