On the Complexity of Many Faces in Arrangements of Circles

Abstract

We obtain improved bounds on the complexity of m distinct faces in an arrangement of n circles and in an arrangement of n unit circles. The bounds are worst-case tight for unit circles, and, for general circles, they nearly coincide with the best known bounds for the number of incidences between m points and n circles.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2002
Accession Number
ADA413626

Entities

People

  • Boris Aronov
  • Micha Sharir
  • Pankaj Agarwal

Organizations

  • Duke University

Tags

DTIC Thesaurus Topics

  • Boundaries
  • Cells
  • Computer Science
  • Computers
  • Construction
  • Crossings
  • Geometry
  • Information Science
  • Laser Peening
  • Lepidoptera
  • Military Research
  • New York
  • Notation
  • Sequences
  • Statistical Sampling
  • Three Dimensional
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.