Computing hereditary convex structures

DOI10.1007/S00454-011-9346-8zbMATH Open1231.68263OpenAlexW4238924095MaRDI QIDQ540446FDOQ540446

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

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

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)

Cites Work

• Introduction to algorithms.
• Applications of random sampling in computational geometry. II
• Filtering Search: A New Approach to Query-Answering
• Title not available (Why is that?)
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• Title not available (Why is that?)
• Computational geometry. Algorithms and applications.
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• A linear algorithm for determining the separation of convex polyhedra
• Triangulating a simple polygon in linear time
• Finding the medial axis of a simple polygon in linear time
• RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Title not available (Why is that?)
• A Randomized Algorithm for Closest-Point Queries
• An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
• Splitting a Delaunay triangulation in linear time
• TRIANGULATING DISJOINT JORDAN CHAINS
• Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
• Sorting helps for Voronoi diagrams
• Three problems about simple polygons
• A tight lower bound for computing the diameter of a 3D convex polytope
• Preprocessing Imprecise Points and Splitting Triangulations
• Title not available (Why is that?)
• Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time
• 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
• Fast detection of polyhedral intersection

Cited In (4)

• Delaunay Triangulation of Imprecise Points Simplified and Extended
• A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• Title not available (Why is that?)

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)