Improved bounds for the union of locally fat objects in the plane

Boris Aronov; Mark De Berg; Esther Ezrar; Micha Sharir

doi:10.1137/120891241

Improved bounds for the union of locally fat objects in the plane

Boris Aronov, Mark De Berg, Esther Ezrar, Micha Sharir

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

Abstract

We show that, for any γ > 0, the combinatorial complexity of the union of n locally γ-fat objects of constant complexity in the plane is nγ4 2O(log n). For the special case of γ-fat triangles,the bound improves to O(n log n + n/γ log2 1/γ ).

Original language	English (US)
Pages (from-to)	543-572
Number of pages	30
Journal	SIAM Journal on Computing
Volume	43
Issue number	2
DOIs	https://doi.org/10.1137/120891241
State	Published - 2014

Keywords

Combinatorial geometry
Fat objects
Union complexity

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/120891241

Cite this

@article{9de808a72ecc45b28ac51e96792a133e,

title = "Improved bounds for the union of locally fat objects in the plane",

abstract = "We show that, for any γ > 0, the combinatorial complexity of the union of n locally γ-fat objects of constant complexity in the plane is nγ4 2O(log n). For the special case of γ-fat triangles,the bound improves to O(n log n + n/γ log2 1/γ ).",

keywords = "Combinatorial geometry, Fat objects, Union complexity",

author = "Boris Aronov and {De Berg}, Mark and Esther Ezrar and Micha Sharir",

year = "2014",

doi = "10.1137/120891241",

language = "English (US)",

volume = "43",

pages = "543--572",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Improved bounds for the union of locally fat objects in the plane

AU - Aronov, Boris

AU - De Berg, Mark

AU - Ezrar, Esther

AU - Sharir, Micha

PY - 2014

Y1 - 2014

N2 - We show that, for any γ > 0, the combinatorial complexity of the union of n locally γ-fat objects of constant complexity in the plane is nγ4 2O(log n). For the special case of γ-fat triangles,the bound improves to O(n log n + n/γ log2 1/γ ).

AB - We show that, for any γ > 0, the combinatorial complexity of the union of n locally γ-fat objects of constant complexity in the plane is nγ4 2O(log n). For the special case of γ-fat triangles,the bound improves to O(n log n + n/γ log2 1/γ ).

KW - Combinatorial geometry

KW - Fat objects

KW - Union complexity

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

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

U2 - 10.1137/120891241

DO - 10.1137/120891241

M3 - Article

AN - SCOPUS:84899626410

SN - 0097-5397

VL - 43

SP - 543

EP - 572

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -

Improved bounds for the union of locally fat objects in the plane

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this