On the complexity of many faces in arrangements of circles

P. K. Agarwal; B. Aronov; M. Sharir

On the complexity of many faces in arrangements of circles

P. K. Agarwal, B. Aronov, M. Sharir

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The many-faces problem for arrangements of circles in the plane was studied. The complexity of many faces and the algorithmic problem arised in a variety of problems including three-dimensional arrangements. The improved bounds on the complexity of m distinct faces in an arrangement of n circles were obtained. The bounds coincide with the best known bounds for the number of incidences between m points and n circles.

Original language	English (US)
Title of host publication	Annual Symposium on Foundations of Computer Science - Proceedings
Pages	74-83
Number of pages	10
State	Published - 2001
Event	42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States Duration: Oct 14 2001 → Oct 17 2001

Other

Other	42nd Annual Symposium on Foundations of Computer Science
Country/Territory	United States
City	Las Vegas, NV
Period	10/14/01 → 10/17/01

ASJC Scopus subject areas

Hardware and Architecture

Cite this

@inproceedings{e9af4f3e979f40779df501ce3b902eec,

title = "On the complexity of many faces in arrangements of circles",

abstract = "The many-faces problem for arrangements of circles in the plane was studied. The complexity of many faces and the algorithmic problem arised in a variety of problems including three-dimensional arrangements. The improved bounds on the complexity of m distinct faces in an arrangement of n circles were obtained. The bounds coincide with the best known bounds for the number of incidences between m points and n circles.",

author = "Agarwal, {P. K.} and B. Aronov and M. Sharir",

year = "2001",

language = "English (US)",

pages = "74--83",

booktitle = "Annual Symposium on Foundations of Computer Science - Proceedings",

note = "42nd Annual Symposium on Foundations of Computer Science ; Conference date: 14-10-2001 Through 17-10-2001",

}

TY - GEN

T1 - On the complexity of many faces in arrangements of circles

AU - Agarwal, P. K.

AU - Aronov, B.

AU - Sharir, M.

PY - 2001

Y1 - 2001

N2 - The many-faces problem for arrangements of circles in the plane was studied. The complexity of many faces and the algorithmic problem arised in a variety of problems including three-dimensional arrangements. The improved bounds on the complexity of m distinct faces in an arrangement of n circles were obtained. The bounds coincide with the best known bounds for the number of incidences between m points and n circles.

AB - The many-faces problem for arrangements of circles in the plane was studied. The complexity of many faces and the algorithmic problem arised in a variety of problems including three-dimensional arrangements. The improved bounds on the complexity of m distinct faces in an arrangement of n circles were obtained. The bounds coincide with the best known bounds for the number of incidences between m points and n circles.

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

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

M3 - Conference contribution

AN - SCOPUS:0035161812

SP - 74

EP - 83

BT - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - 42nd Annual Symposium on Foundations of Computer Science

Y2 - 14 October 2001 through 17 October 2001

ER -

On the complexity of many faces in arrangements of circles

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this