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

Research output: Contribution to journalConference articlepeer-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 (FOCS'00), which provided a weaker bound for a restricted class of curves (graphs of degree-s polynomials) only. 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)544-550
Number of pages7
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 2 2003
Externally publishedYes
EventProceedings: 44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003 - Cambridge, MA, United States
Duration: Oct 11 2003Oct 14 2003

ASJC Scopus subject areas

  • Hardware and Architecture

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