Combinatorial complexity of hyperplane transversals

Sylvain E. Cappell, Richard Pollack, Jacob E. Goodman, Micha Sharir, Janos Pach, Rephael Wenger

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

Abstract

We show that the maximum combinatorial complexity of the space of hyperplane transversals to a family of n separated and strictly convex sets in Rd is Θ(nd/2), which generalizes results of Edelsbrunner and Sharir in the plane. As a key step in the argument, we show that the space of hyperplanes tangent to k ≤ d separated and strictly convex sets in Rd is a topological (d - k)-sphere.

Original languageEnglish (US)
Title of host publicationProc Sixth Annu Symp Comput Geom
PublisherPubl by ACM
Pages83-91
Number of pages9
ISBN (Print)0897913620, 9780897913621
DOIs
StatePublished - 1990
EventProceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA
Duration: Jun 6 1990Jun 8 1990

Publication series

NameProc Sixth Annu Symp Comput Geom

Conference

ConferenceProceedings of the Sixth Annual Symposium on Computational Geometry
CityBerkeley, CA, USA
Period6/6/906/8/90

ASJC Scopus subject areas

  • General Engineering

Cite this