Computing hereditary convex structures
Motivated by a question of \textit{A. Aggarwal, L. J. Guibas, J. Saxe} and \textit{P. W. Shor} [Discrete Comput. Geom. 4, No. 6, 591--604 (1989; Zbl 0696.68045)], the first theorem of the authors shows that given any set \(P\) of \(n\) points in \({\mathbb R}^3\) in general convex position, colored red and blue, and given the convex hull of \(P\), the convex hull of the blue points can be computed in \(O(n)\) expected time. Then the authors extend this result to an arbitrary number of colors. Here they prove that the convex hull of all the color classes can be computed in \(O(n\sqrt{\log n})\) expected time, and, surprisingly, in linear time if the coloring is random. They also consider other cases of hereditary computation.
- A linear algorithm for determining the separation of convex polyhedra
- A linear-time algorithm for computing the Voronoi diagram of a convex polygon
- A Randomized Algorithm for Closest-Point Queries
- 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
- 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?)
- 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
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase(\le k)-Levels in Three Dimensions
- RANDOMIZATION YIELDS SIMPLE O(n log⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
- Sorting helps for Voronoi diagrams
- Splitting a Delaunay triangulation in linear time
- Three problems about simple polygons
- Triangulating a simple polygon in linear time
- TRIANGULATING DISJOINT JORDAN CHAINS
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)
