Empty pseudo-triangles in point sets

DOI10.1016/J.DAM.2011.07.026MaRDI QIDQ765318zbMATH OpenOpenAlexWikidataFDO

Authors Hee-Kap Ahn, Sang Won Bae, Iris Reinbacher, Bettina Speckmann, Marc Van Kreveld

Publication date 19 March 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.07.026

zbMATH Keywords

finite planar point setoptimal pseudo-triangle computationpseudo-triangle count

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of finite geometries (05B25) Combinatorial structures in finite projective spaces (51E20) Euclidean geometries (general) and generalizations (51M05)

Recommendations

• Holes or empty pseudo-triangles in planar point sets
• On numbers of pseudo-triangulations
• On the number of pseudo-empty convex pentagons for a planar point set
• Tight degree bounds for pseudo-triangulations of points
• Enumerating pseudo-triangulations in the plane

Cites work

• scientific article; zbMATH DE number 3630765 (Why is no real title available?)
• scientific article; zbMATH DE number 2209740 (Why is no real title available?)
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• An efficient algorithm for determining the convex hull of a finite planar set
• Computational geometry. Algorithms and applications.
• Convexity minimizes pseudo-triangulations
• Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
• Empty Simplices in Euclidean Space
• Largest empty rectangle among a point set
• Minimum weight pseudo-triangulations
• On the number of pseudo-triangulations of certain point sets
• Planar point sets with a small number of empty convex polygons
• Planar sets with few empty convex polygons
• Pseudo-triangulations -- a survey
• Sets with No Empty Convex 7-Gons
• THE VISIBILITY COMPLEX
• Topologically sweeping an arrangement
• Topologically sweeping visibility complexes via pseudotriangulations

Cited in

(7)

• Convexity minimizes pseudo-triangulations
• On constrained minimum pseudotriangulations
• On numbers of pseudo-triangulations
• Holes or empty pseudo-triangles in planar point sets
• Tight degree bounds for pseudo-triangulations of points
• Searching for empty convex polygons
• On the number of pseudo-empty convex pentagons for a planar point set

This page was built for publication: Empty pseudo-triangles in point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765318)