Computing hereditary convex structures (Q540446): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
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 |
Revision as of 11:05, 1 July 2023
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