Computing hereditary convex structures (Q540446): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Martin Henk / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68U05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 52B55 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 52B10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5903705 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
convex polytope | |||
Property / zbMATH Keywords: convex polytope / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
hereditary convex hull | |||
Property / zbMATH Keywords: hereditary convex hull / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
splitting convex polytopes | |||
Property / zbMATH Keywords: splitting convex polytopes / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00454-011-9346-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4238924095 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A linear-time algorithm for computing the Voronoi diagram of a convex polygon / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Linear-time triangulation of a simple polygon made easier via randomization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: TRIANGULATING DISJOINT JORDAN CHAINS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5452284 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4217293 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Delaunay Triangulations in O(sort(n)) Time and More / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Three problems about simple polygons / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Filtering Search: A New Approach to Query-Answering / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Triangulating a simple polygon in linear time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4515159 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Splitting a Delaunay triangulation in linear time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finding the medial axis of a simple polygon in linear time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Randomized Algorithm for Closest-Point Queries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Applications of random sampling in computational geometry. II / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3651735 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: RANDOMIZATION YIELDS SIMPLE O(n <font>log</font><sup>⋆</sup> n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ON COMPUTING VORONOI DIAGRAMS FOR SORTED POINT SETS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast detection of polyhedral intersection / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A linear algorithm for determining the separation of convex polyhedra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A tight lower bound for computing the diameter of a 3D convex polytope / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sorting helps for Voronoi diagrams / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Preprocessing Imprecise Points and Splitting Triangulations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4530626 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3716336 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 03:36, 4 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computing hereditary convex structures |
scientific article |
Statements
Computing hereditary convex structures (English)
0 references
3 June 2011
0 references
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.
0 references
convex polytope
0 references
hereditary convex hull
0 references
splitting convex polytopes
0 references
0 references
0 references
0 references