TY - GEN
T1 - Computing hereditary convex structures
AU - Chazelle, Bernard
AU - Mulzer, Wolfgang
PY - 2009
Y1 - 2009
N2 - Color red and blue the n vertices of a convex polytope P in ℝ3. Can we compute the convex hull of each color class in o(n log n)? What if we have x > 2 colors? What if the colors are random? Consider an arbitrary query halfspace and call the vertices of 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.
AB - Color red and blue the n vertices of a convex polytope P in ℝ3. Can we compute the convex hull of each color class in o(n log n)? What if we have x > 2 colors? What if the colors are random? Consider an arbitrary query halfspace and call the vertices of 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.
KW - Convex polytope
KW - Half-space range searching
KW - Hereditary convex hulls
UR - http://www.scopus.com/inward/record.url?scp=70849112136&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70849112136&partnerID=8YFLogxK
U2 - 10.1145/1542362.1542374
DO - 10.1145/1542362.1542374
M3 - Conference contribution
AN - SCOPUS:70849112136
SN - 9781605585017
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 61
EP - 70
BT - Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09
T2 - 25th Annual Symposium on Computational Geometry, SCG'09
Y2 - 8 June 2009 through 10 June 2009
ER -