Empty pseudo-triangles in point sets

DOI10.1016/j.dam.2011.07.026zbMath1237.51012WikidataQ59782298 ScholiaQ59782298MaRDI QIDQ765318

Iris Reinbacher, Sang Won Bae, Bettina Speckmann, Hee-Kap Ahn, Marc J. 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 set; optimal pseudo-triangle computation; pseudo-triangle count

Mathematics Subject Classification ID

90C27: Combinatorial optimization

05B25: Combinatorial aspects of finite geometries

51E20: Combinatorial structures in finite projective spaces

51M05: Euclidean geometries (general) and generalizations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convexity minimizes pseudo-triangulations
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• Topologically sweeping an arrangement
• Topologically sweeping visibility complexes via pseudotriangulations
• Minimum weight pseudo-triangulations
• Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
• On the number of pseudo-triangulations of certain point sets
• An efficient algorithm for determining the convex hull of a finite planar set
• Planar sets with few empty convex polygons
• Sets with No Empty Convex 7-Gons
• Empty Simplices in Euclidean Space
• Largest empty rectangle among a point set
• THE VISIBILITY COMPLEX
• Planar point sets with a small number of empty convex polygons