On levels in arrangements of surfaces in three dimensions

Timothy M. Chan

On levels in arrangements of surfaces in three dimensions

Research output: Contribution to conference › Paper › peer-review

Abstract

A favorite open problem in combinatorial geometry is to determine the worst-case complexity of a level in an arrangement. Up to now, nontrivial upper bounds in three dimensions are known only for the linear cases of planes and triangles. We propose the first technique that can deal with more general surfaces in three dimensions. For example, in an arrangement of n "pseudo-planes" or "pseudo-spheres" (where each triple of surfaces has at most two common intersections), we prove that there are at most O(n^2.9986) vertices of any given level.

Original language	English (US)
Pages	232-240
Number of pages	9
State	Published - 2005
Externally published	Yes
Event	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005

Other

Other	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Vancouver, BC
Period	1/23/05 → 1/25/05

ASJC Scopus subject areas

Software
General Mathematics

Library availability

Discover UIUC Full Text

Cite this

@conference{4afba7469c164589954ba6bd2ec6f831,

title = "On levels in arrangements of surfaces in three dimensions",

abstract = "A favorite open problem in combinatorial geometry is to determine the worst-case complexity of a level in an arrangement. Up to now, nontrivial upper bounds in three dimensions are known only for the linear cases of planes and triangles. We propose the first technique that can deal with more general surfaces in three dimensions. For example, in an arrangement of n {"}pseudo-planes{"} or {"}pseudo-spheres{"} (where each triple of surfaces has at most two common intersections), we prove that there are at most O(n2.9986) vertices of any given level.",

author = "Chan, {Timothy M.}",

year = "2005",

language = "English (US)",

pages = "232--240",

}

TY - CONF

T1 - On levels in arrangements of surfaces in three dimensions

AU - Chan, Timothy M.

PY - 2005

Y1 - 2005

N2 - A favorite open problem in combinatorial geometry is to determine the worst-case complexity of a level in an arrangement. Up to now, nontrivial upper bounds in three dimensions are known only for the linear cases of planes and triangles. We propose the first technique that can deal with more general surfaces in three dimensions. For example, in an arrangement of n "pseudo-planes" or "pseudo-spheres" (where each triple of surfaces has at most two common intersections), we prove that there are at most O(n2.9986) vertices of any given level.

AB - A favorite open problem in combinatorial geometry is to determine the worst-case complexity of a level in an arrangement. Up to now, nontrivial upper bounds in three dimensions are known only for the linear cases of planes and triangles. We propose the first technique that can deal with more general surfaces in three dimensions. For example, in an arrangement of n "pseudo-planes" or "pseudo-spheres" (where each triple of surfaces has at most two common intersections), we prove that there are at most O(n2.9986) vertices of any given level.

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

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

M3 - Paper

AN - SCOPUS:20744439831

SP - 232

EP - 240

T2 - Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 23 January 2005 through 25 January 2005

ER -

On levels in arrangements of surfaces in three dimensions

Abstract

Other

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this