skip to main content
10.1145/1137856.1137899acmconferencesArticle/Chapter ViewAbstractPublication PagessocgConference Proceedingsconference-collections
Article

Pre-triangulations and liftable complexes

Published: 05 June 2006 Publication History

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]
O. Aichholzer, F. Aurenhammer, H. Krasser, P. Brass. Pseudo-triangulations from surfaces and a novel type of edge flip. SIAM Journal on Computing 32 (2003), 1621--1653.
[2]
F. Aurenhammer. Voronoi diagrams -- a survey of a fundamental geometric data structure. ACM Computing Surveys 23 (1991), 345--405.
[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]
H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, 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]
C. L. Lawson.Properties of n-dimensional triangulations. Computer Aided Geometric Design 3 (1986), 231--246.
[17]
D.T.Lee, A.K.Lin. Generalized Delaunay triangulation for planar graphs. Discrete & Computational Geometry 1 (1986), 201--217.
[18]
D.Orden, F.Santos. The polytope of non-crossing graphs on a planar point set. Discrete & Computational Geometry 33 (2005), 275--305.
[19]
M. Pocchiola, G. Vegter, Topologically sweeping visibility complexes via pseudo-triangulations. Discrete & Computational Geometry 16 (1996), 419--453.
[20]
F.P.Preparata, M.I.Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 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]
K.Sugihara. Machine Interpretation of Line Drawings. MIT Press, Cambridge, 1986.
[24]
I.Streinu. A combinatorial approach to planar non-colliding robot arm motion planning. Proc. 41st IEEE Symp. FOCS, 2000, 443--453.

Cited By

View all
  • (2008)Flip Algorithm for Segment TriangulationsProceedings of the 33rd international symposium on Mathematical Foundations of Computer Science10.1007/978-3-540-85238-4_14(180-192)Online publication date: 25-Aug-2008
  • (2007)Triangulations of line segment sets in the planeProceedings of the 27th international conference on Foundations of software technology and theoretical computer science10.5555/1781794.1781828(388-399)Online publication date: 12-Dec-2007
  • (2007)Triangulations of Line Segment Sets in the PlaneFSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science10.1007/978-3-540-77050-3_32(388-399)Online publication date: 2007

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry
June 2006
500 pages
ISBN:1595933409
DOI:10.1145/1137856
  • Program Chairs:
  • Nina Amenta,
  • Otfried Cheong
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2006

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SoCG06

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2008)Flip Algorithm for Segment TriangulationsProceedings of the 33rd international symposium on Mathematical Foundations of Computer Science10.1007/978-3-540-85238-4_14(180-192)Online publication date: 25-Aug-2008
  • (2007)Triangulations of line segment sets in the planeProceedings of the 27th international conference on Foundations of software technology and theoretical computer science10.5555/1781794.1781828(388-399)Online publication date: 12-Dec-2007
  • (2007)Triangulations of Line Segment Sets in the PlaneFSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science10.1007/978-3-540-77050-3_32(388-399)Online publication date: 2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media