Combinatorial complexity of hyperplane transversals

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

doi:10.1145/98524.98542

Combinatorial complexity of hyperplane transversals

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

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 R^d is Θ(n^d/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 R^d is a topological (d - k)-sphere.

Original language	English (US)
Title of host publication	Proc Sixth Annu Symp Comput Geom
Publisher	Publ by ACM
Pages	83-91
Number of pages	9
ISBN (Print)	0897913620, 9780897913621
DOIs	https://doi.org/10.1145/98524.98542
State	Published - 1990
Event	Proceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA Duration: Jun 6 1990 → Jun 8 1990

Publication series

Name	Proc Sixth Annu Symp Comput Geom

Conference

Conference	Proceedings of the Sixth Annual Symposium on Computational Geometry
City	Berkeley, CA, USA
Period	6/6/90 → 6/8/90

ASJC Scopus subject areas

General Engineering

Access to Document

10.1145/98524.98542

Cite this

@inproceedings{32617968b53041a8a245dbb064139905,

title = "Combinatorial complexity of hyperplane transversals",

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

author = "Cappell, {Sylvain E.} and Richard Pollack and Goodman, {Jacob E.} and Micha Sharir and Janos Pach and Rephael Wenger",

year = "1990",

doi = "10.1145/98524.98542",

language = "English (US)",

isbn = "0897913620",

series = "Proc Sixth Annu Symp Comput Geom",

publisher = "Publ by ACM",

pages = "83--91",

booktitle = "Proc Sixth Annu Symp Comput Geom",

note = "Proceedings of the Sixth Annual Symposium on Computational Geometry ; Conference date: 06-06-1990 Through 08-06-1990",

}

TY - GEN

T1 - Combinatorial complexity of hyperplane transversals

AU - Cappell, Sylvain E.

AU - Pollack, Richard

AU - Goodman, Jacob E.

AU - Sharir, Micha

AU - Pach, Janos

AU - Wenger, Rephael

PY - 1990

Y1 - 1990

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0025070652&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025070652&partnerID=8YFLogxK

U2 - 10.1145/98524.98542

DO - 10.1145/98524.98542

M3 - Conference contribution

AN - SCOPUS:0025070652

SN - 0897913620

SN - 9780897913621

T3 - Proc Sixth Annu Symp Comput Geom

SP - 83

EP - 91

BT - Proc Sixth Annu Symp Comput Geom

PB - Publ by ACM

T2 - Proceedings of the Sixth Annual Symposium on Computational Geometry

Y2 - 6 June 1990 through 8 June 1990

ER -

Combinatorial complexity of hyperplane transversals

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this