On the complexity of arrangements of circles in the plane

N. Alon; H. Last; R. Pinchasi; M. Sharir

doi:10.1007/s00454-001-0043-x

On the complexity of arrangements of circles in the plane

N. Alon, H. Last, R. Pinchasi, M. Sharir

Research output: Contribution to journal › Article › peer-review

23 Scopus citations

Abstract

Continuing and extending the analysis in a previous paper [15], we establish several combinatorial results on the complexity of arrangements of circles in the plane. The main results are a collection of partial solutions to the conjecture that (a) any arrangement of unit circles with at least one intersecting pair has a vertex incident to at most three circles, and (b) any arrangement of circles of arbitrary radii with at least one intersecting pair has a vertex incident to at most three circles, under appropriate assumptions on the number of intersecting pairs of circles (see below for a more precise statement).

Original language	English (US)
Pages (from-to)	465-492
Number of pages	28
Journal	Discrete and Computational Geometry
Volume	26
Issue number	4
DOIs	https://doi.org/10.1007/s00454-001-0043-x
State	Published - Dec 2001
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1007/s00454-001-0043-x

Cite this

@article{c56c68683d304ad9a60ca804c68386c9,

title = "On the complexity of arrangements of circles in the plane",

abstract = "Continuing and extending the analysis in a previous paper [15], we establish several combinatorial results on the complexity of arrangements of circles in the plane. The main results are a collection of partial solutions to the conjecture that (a) any arrangement of unit circles with at least one intersecting pair has a vertex incident to at most three circles, and (b) any arrangement of circles of arbitrary radii with at least one intersecting pair has a vertex incident to at most three circles, under appropriate assumptions on the number of intersecting pairs of circles (see below for a more precise statement).",

author = "N. Alon and H. Last and R. Pinchasi and M. Sharir",

year = "2001",

month = dec,

doi = "10.1007/s00454-001-0043-x",

language = "English (US)",

volume = "26",

pages = "465--492",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - On the complexity of arrangements of circles in the plane

AU - Alon, N.

AU - Last, H.

AU - Pinchasi, R.

AU - Sharir, M.

PY - 2001/12

Y1 - 2001/12

N2 - Continuing and extending the analysis in a previous paper [15], we establish several combinatorial results on the complexity of arrangements of circles in the plane. The main results are a collection of partial solutions to the conjecture that (a) any arrangement of unit circles with at least one intersecting pair has a vertex incident to at most three circles, and (b) any arrangement of circles of arbitrary radii with at least one intersecting pair has a vertex incident to at most three circles, under appropriate assumptions on the number of intersecting pairs of circles (see below for a more precise statement).

AB - Continuing and extending the analysis in a previous paper [15], we establish several combinatorial results on the complexity of arrangements of circles in the plane. The main results are a collection of partial solutions to the conjecture that (a) any arrangement of unit circles with at least one intersecting pair has a vertex incident to at most three circles, and (b) any arrangement of circles of arbitrary radii with at least one intersecting pair has a vertex incident to at most three circles, under appropriate assumptions on the number of intersecting pairs of circles (see below for a more precise statement).

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

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

U2 - 10.1007/s00454-001-0043-x

DO - 10.1007/s00454-001-0043-x

M3 - Article

AN - SCOPUS:0035623196

SN - 0179-5376

VL - 26

SP - 465

EP - 492

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -

On the complexity of arrangements of circles in the plane

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this