On levels in arrangements of curves, II: A simple inequality and its consequences

Research output: Contribution to journalArticlepeer-review

Abstract

We give a surprisingly short proof that in any planar arrangement of n curves where each pair intersects at most a fixed number (s) of times, the k-level has subquadratic (O(n2-1/2s) complexity. This answers one of the main open problems from the author's previous paper [DCG 29, 375-393 (2003)], which provided a weaker upper bound for a restricted class of curves only (graphs of degree-s polynomials). When combined with existing tools (cutting curves, sampling, etc.), the new idea generates a slew of improved k-level results for most of the curve families studied earlier, including a near-O(n3/2 bound for parabolas.

Original languageEnglish (US)
Pages (from-to)11-24
Number of pages14
JournalDiscrete and Computational Geometry
Volume34
Issue number1
DOIs
StatePublished - Jul 2005
Externally publishedYes

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 curves, II: A simple inequality and its consequences'. Together they form a unique fingerprint.

Cite this