The common exterior of convex polygons in the plane

Boris Aronov; Micha Sharir

doi:10.1016/S0925-7721(96)00004-1

The common exterior of convex polygons in the plane

Boris Aronov, Micha Sharir

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

Abstract

We establish several combinatorial bounds on the complexity (number of vertices and edges) of the complement of the union (also known as the common exterior) of k convex polygons in the plane, with a total of n edges. We show: (1) The maximum complexity of the entire common exterior is Θ(na(k) + k²). ² (2) The maximum complexity of a single cell of the common exterior is Θ(na(k)). (3) The complexity of m distinct cells in the common exterior is O(m^2/3k^2/3log^1/3(k²/m) + n log k) and can be Ω(m^2/3k^2/3 + na(k)) in the worst case.

Original language	English (US)
Pages (from-to)	139-149
Number of pages	11
Journal	Computational Geometry: Theory and Applications
Volume	8
Issue number	3
DOIs	https://doi.org/10.1016/S0925-7721(96)00004-1
State	Published - Aug 1997

Keywords

Arrangements
Combinatorial complexity
Common exterior
Convex polygons

ASJC Scopus subject areas

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/S0925-7721(96)00004-1

Cite this

@article{ee96a7c7693048398dc7e2633030a4a6,

title = "The common exterior of convex polygons in the plane",

abstract = "We establish several combinatorial bounds on the complexity (number of vertices and edges) of the complement of the union (also known as the common exterior) of k convex polygons in the plane, with a total of n edges. We show: (1) The maximum complexity of the entire common exterior is Θ(na(k) + k2). 2 (2) The maximum complexity of a single cell of the common exterior is Θ(na(k)). (3) The complexity of m distinct cells in the common exterior is O(m2/3k2/3log1/3(k2/m) + n log k) and can be Ω(m2/3k2/3 + na(k)) in the worst case.",

keywords = "Arrangements, Combinatorial complexity, Common exterior, Convex polygons",

author = "Boris Aronov and Micha Sharir",

note = "Funding Information: * Corresponding author. Supported by NSF Grant CCR-92-11541 and a Sloan Research Fellowship. i Supported by NSF Grants CCR-91-22103, CCR-93-11127, and CCR-94-24398, by a Max-Plank Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. 2 Here and thereafter c~(n) denotes the functional inverse of the Ackermann's function.",

year = "1997",

month = aug,

doi = "10.1016/S0925-7721(96)00004-1",

language = "English (US)",

volume = "8",

pages = "139--149",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - The common exterior of convex polygons in the plane

AU - Aronov, Boris

AU - Sharir, Micha

N1 - Funding Information: * Corresponding author. Supported by NSF Grant CCR-92-11541 and a Sloan Research Fellowship. i Supported by NSF Grants CCR-91-22103, CCR-93-11127, and CCR-94-24398, by a Max-Plank Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. 2 Here and thereafter c~(n) denotes the functional inverse of the Ackermann's function.

PY - 1997/8

Y1 - 1997/8

N2 - We establish several combinatorial bounds on the complexity (number of vertices and edges) of the complement of the union (also known as the common exterior) of k convex polygons in the plane, with a total of n edges. We show: (1) The maximum complexity of the entire common exterior is Θ(na(k) + k2). 2 (2) The maximum complexity of a single cell of the common exterior is Θ(na(k)). (3) The complexity of m distinct cells in the common exterior is O(m2/3k2/3log1/3(k2/m) + n log k) and can be Ω(m2/3k2/3 + na(k)) in the worst case.

AB - We establish several combinatorial bounds on the complexity (number of vertices and edges) of the complement of the union (also known as the common exterior) of k convex polygons in the plane, with a total of n edges. We show: (1) The maximum complexity of the entire common exterior is Θ(na(k) + k2). 2 (2) The maximum complexity of a single cell of the common exterior is Θ(na(k)). (3) The complexity of m distinct cells in the common exterior is O(m2/3k2/3log1/3(k2/m) + n log k) and can be Ω(m2/3k2/3 + na(k)) in the worst case.

KW - Arrangements

KW - Combinatorial complexity

KW - Common exterior

KW - Convex polygons

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

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

U2 - 10.1016/S0925-7721(96)00004-1

DO - 10.1016/S0925-7721(96)00004-1

M3 - Article

AN - SCOPUS:0040360922

SN - 0925-7721

VL - 8

SP - 139

EP - 149

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 3

ER -

The common exterior of convex polygons in the plane

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this