Computing hereditary convex structures (Q540446)

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.