Computing hereditary convex structures (Q540446)
From MaRDI portal
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