Computing hereditary convex structures

Bernard Chazelle; Wolfgang Mulzer

doi:10.1145/1542362.1542374

Computing hereditary convex structures

Bernard Chazelle, Wolfgang Mulzer

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

Color red and blue the n vertices of a convex polytope P in ℝ³. 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 language	English (US)
Title of host publication	Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09
Pages	61-70
Number of pages	10
DOIs	https://doi.org/10.1145/1542362.1542374
State	Published - 2009
Event	25th Annual Symposium on Computational Geometry, SCG'09 - Aarhus, Denmark Duration: Jun 8 2009 → Jun 10 2009

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry

Other

Other	25th Annual Symposium on Computational Geometry, SCG'09
Country/Territory	Denmark
City	Aarhus
Period	6/8/09 → 6/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

Access to Document

10.1145/1542362.1542374

Cite this

@inproceedings{db1b7d43165e42e5b85dd7389e5173d6,

title = "Computing hereditary convex structures",

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.",

keywords = "Convex polytope, Half-space range searching, Hereditary convex hulls",

author = "Bernard Chazelle and Wolfgang Mulzer",

year = "2009",

doi = "10.1145/1542362.1542374",

language = "English (US)",

isbn = "9781605585017",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "61--70",

booktitle = "Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09",

note = "25th Annual Symposium on Computational Geometry, SCG'09 ; Conference date: 08-06-2009 Through 10-06-2009",

}

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 -

Computing hereditary convex structures

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this