Computing hereditary convex structures

DOI10.1007/S00454-011-9346-8MaRDI QIDQ540446zbMATH OpenOpenAlexFDO

Authors Bernard Chazelle, Wolfgang Mulzer

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 polytopehereditary convex hullsplitting convex polytopes

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Three-dimensional polytopes (52B10) Computational aspects related to convexity (52B55)

Recommendations

• Computing hereditary convex structures
• scientific article; zbMATH DE number 2123362
• scientific article; zbMATH DE number 1182912
• An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem
• A linear algorithm for computing convex hulls for random lines

Cites work

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

Cited in

(4)

• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• Computing hereditary convex structures
• Delaunay Triangulation of Imprecise Points Simplified and Extended
• Triangles and girth in disk graphs and transmission graphs

This page was built for publication: Computing hereditary convex structures

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