Computing hereditary convex structures

Bernard Chazelle, Wolfgang Mulzer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual Symposium on Computational Geometry, SCG'09
Pages61-70
Number of pages10
DOIs
StatePublished - Dec 4 2009
Event25th Annual Symposium on Computational Geometry, SCG'09 - Aarhus, Denmark
Duration: Jun 8 2009Jun 10 2009

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other25th Annual Symposium on Computational Geometry, SCG'09
CountryDenmark
CityAarhus
Period6/8/096/10/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Keywords

  • Convex polytope
  • Half-space range searching
  • Hereditary convex hulls

Fingerprint Dive into the research topics of 'Computing hereditary convex structures'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., & Mulzer, W. (2009). Computing hereditary convex structures. In Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09 (pp. 61-70). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1542362.1542374