We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Computing Hereditary Convex Structures.
- Authors
Chazelle, Bernard; Mulzer, Wolfgang
- Abstract
Color red and blue the n vertices of a convex polytope $\mathcal{P}$ in ℝ. Can we compute the convex hull of each color class in o( nlog n) time? What if we have more than two colors? What if the colors are random? Consider an arbitrary query halfspace and call the vertices of $\mathcal{P}$ inside it blue: can the convex hull of the blue points be computed in time linear in their number? More generally, can we quickly compute the blue hull without looking at the whole polytope? This paper considers several instances of hereditary computation and provides new results for them. In particular, we resolve an eight-year old open problem by showing how to split a convex polytope in linear expected time.
- Subjects
CONVEX geometry; POLYTOPES; LINEAR time invariant systems; ANALYSIS of colors; BLUE; RED
- Publication
Discrete & Computational Geometry, 2011, Vol 45, Issue 4, p796
- ISSN
0179-5376
- Publication type
Article
- DOI
10.1007/s00454-011-9346-8