Checking the convexity of polytopes and the planarity of subdivisions

DOI10.1016/S0925-7721(98)00039-XzbMath0921.68101OpenAlexW2033866653MaRDI QIDQ1276945

Giuseppe Liotta, Roberto Tamassia, Olivier Devillers, Franco P. Preparata

Publication date: 11 April 1999

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(98)00039-x

zbMATH Keywords

Delaunay triangulationsconvex subdivisions

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (11)

Planar straight-line realizations of 2-trees with prescribed edge lengths ⋮ Constructing convex 3-polytopes from two triangulations of a polygon ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ Certifying algorithms ⋮ An efficient local approach to convexity testing of piecewise-linear hypersurfaces ⋮ Pipelined algorithms to detect cheating in long-term grid computations ⋮ Efficient authenticated data structures for graph connectivity and geometric search problems ⋮ Every collinear set in a planar graph is free ⋮ A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING ⋮ Triangulations of Line Segment Sets in the Plane ⋮ Triangulations in CGAL

Cites Work

• Unnamed Item
• Unnamed Item
• Towards exact geometric computation
• On approximation behavior of the greedy triangulation for convex polygons
• Establishing order in planar subdivisions
• Triangulating a simple polygon in linear time
• Parallel concepts in graph theory
• Incremental convex planarity testing
• Algorithms for Reporting and Counting Geometric Intersections
• Efficient Planarity Testing
• Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design
• Designing programs that check their work
• Certification of computational results
• Angles of Planar Triangular Graphs

This page was built for publication: Checking the convexity of polytopes and the planarity of subdivisions