Computing hereditary convex structures

DOI10.1007/s00454-011-9346-8zbMath1231.68263MaRDI QIDQ540446

Wolfgang Mulzer, Bernard Chazelle

Publication date: 3 June 2011

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-011-9346-8

zbMATH Keywords

convex polytope; hereditary convex hull; splitting convex polytopes

Mathematics Subject Classification ID

52B10: Three-dimensional polytopes

52B55: Computational aspects related to convexity

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

Related Items

A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations, Preprocessing imprecise points for Delaunay triangulation: simplified and extended, Delaunay Triangulation of Imprecise Points Simplified and Extended

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast detection of polyhedral intersection
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Triangulating a simple polygon in linear time
• Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
• Finding the medial axis of a simple polygon in linear time
• Sorting helps for Voronoi diagrams
• Applications of random sampling in computational geometry. II
• Splitting a Delaunay triangulation in linear time
• Three problems about simple polygons
• A tight lower bound for computing the diameter of a 3D convex polytope
• Preprocessing Imprecise Points and Splitting Triangulations
• A linear algorithm for determining the separation of convex polyhedra
• Filtering Search: A New Approach to Query-Answering
• A Randomized Algorithm for Closest-Point Queries
• RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
• An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
• Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time
• TRIANGULATING DISJOINT JORDAN CHAINS
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• ON COMPUTING VORONOI DIAGRAMS FOR SORTED POINT SETS
• Delaunay Triangulations in O(sort(n)) Time and More
• Linear-time triangulation of a simple polygon made easier via randomization