Pre-triangulations and liftable complexes

ABSTRACT

We introduce and discuss the concept of pre-triangulations, a relaxation of triangulations that goes beyond the well-established class of pseudo-triangulations.

REFERENCES

• 1: Oswin Aichholzer , Franz Aurenhammer , Hannes Krasser , Peter Brass, Pseudotriangulations from Surfaces and a Novel Type of Edge Flip, SIAM Journal on Computing, v.32 n.6, p.1621-1653, 2003 [doi>10.1137/S0097539702411368]
• 2: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 3: 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.
• 4: F. Aurenhammer, T. Hackl, H. Krasser. Short flip sequences for constructing the Delaunay triangulation. Manuscript, 2006.
• 5: F. Aurenhammer, H. Krasser. Pseudo-simplicial complexes from maximal locally convex functions. Discrete & Computational Geometry 35 (2006), 201--221.
• 6: 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.
• 7: A. Brøndsted. An Introduction to Convex Polytopes. Springer Verlag, 1983.
• 8: H. Crapo, W. Whiteley. Plane self stresses and projected polyhedra. Structural Topology 20 (1993), 55--78.
• 9: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 10: H. Edelsbrunner, N. R. Shah. Incremental topological flipping works for regular triangulations. Algorithmica 15 (1996), 223--241.
• 11: 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.
• 12: B. Grünbaum. Convex Polytopes. Wiley Interscience, London, 1967.
• 13: T. Hackl. Manipulation of Pseudo-Triangular Surfaces. Master Thesis, Institute for Theoretical Computer Science, University of Technology, Graz, Austria, 2004.
• 14: C.Huemer. Flip Operations for Geometric and Combinatorial Objects. Master Thesis, Institute for Theoretical Computer Science, University of Technology, Graz, Austria, 2003.
• 15: F. Hurtado, M. Noy, J. Urrutia. Flipping edges in triangulations. Discrete & Computational Geometry 22 (1999), 333--346.
• 16: 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]
• 17: D.T.Lee, A.K.Lin. Generalized Delaunay triangulation for planar graphs. Discrete & Computational Geometry 1 (1986), 201--217.
• 18: David Orden , Francisco Santos, The Polytope of Non-Crossing Graphs on a Planar Point Set, Discrete & Computational Geometry, v.33 n.2, p.275-305, February 2005 [doi>10.1007/s00454-004-1143-1]
• 19: M. Pocchiola, G. Vegter, Topologically sweeping visibility complexes via pseudo-triangulations. Discrete & Computational Geometry 16 (1996), 419--453.
• 20: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 21: G.Rote, A.Schulz. A pointed Delaunay pseudo-triangulation of a simple polygon. Proc. 21st European Workshop on Computational Geometry, 2005, 77--80.
• 22: E.Steinitz. Polyeder und Raumeinteilungen. Enzyklopaedie der Math. Wiss. III AB 12, Leipzig, 1916.
• 23: Kokichi Sugihara, Machine interpretation of line drawings, MIT Press, Cambridge, MA, 1986
• 24: 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

General Terms:
Algorithms, Theory