On levels in arrangements of surfaces in three dimensions

Research output: Contribution to journalArticlepeer-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-spherical patches" (where the main criterion is that each triple of surfaces has at most two common intersections), we prove that there are at most O(n 2.997) vertices at any given level.

Original languageEnglish (US)
Pages (from-to)1-18
Number of pages18
JournalDiscrete and Computational Geometry
Volume48
Issue number1
DOIs
StatePublished - Jul 2012

Keywords

  • Arrangements
  • The k-set problem
  • k-Level

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On levels in arrangements of surfaces in three dimensions'. Together they form a unique fingerprint.

Cite this