Improved bounds on the union complexity of fat objects

M. Berg, de

doi:10.1007/s00454-007-9029-7

Improved bounds on the union complexity of fat objects

M. Berg, de

Algorithms

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

26 Citations (Scopus)

Abstract

We introduce a new class of fat, not necessarily convex or polygonal, objects in the plane, namely locally ¿-fat objects. We prove that the union complexity of any set of n such objects is O(¿ s+2(n)log¿2 n). This improves the best known bound, and extends it to a more general class of objects.

Original language	English
Pages (from-to)	127-140
Journal	Discrete and Computational Geometry
Volume	40
Issue number	1
DOIs	https://doi.org/10.1007/s00454-007-9029-7
Publication status	Published - 2008

Access to Document

10.1007/s00454-007-9029-7

Cite this

@article{65fe79c5085d48ff8154f4b4e3b2eb0b,

title = "Improved bounds on the union complexity of fat objects",

abstract = "We introduce a new class of fat, not necessarily convex or polygonal, objects in the plane, namely locally ¿-fat objects. We prove that the union complexity of any set of n such objects is O(¿ s+2(n)log¿2 n). This improves the best known bound, and extends it to a more general class of objects.",

author = "{Berg, de}, M.",

year = "2008",

doi = "10.1007/s00454-007-9029-7",

language = "English",

volume = "40",

pages = "127--140",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Improved bounds on the union complexity of fat objects

AU - Berg, de, M.

PY - 2008

Y1 - 2008

N2 - We introduce a new class of fat, not necessarily convex or polygonal, objects in the plane, namely locally ¿-fat objects. We prove that the union complexity of any set of n such objects is O(¿ s+2(n)log¿2 n). This improves the best known bound, and extends it to a more general class of objects.

AB - We introduce a new class of fat, not necessarily convex or polygonal, objects in the plane, namely locally ¿-fat objects. We prove that the union complexity of any set of n such objects is O(¿ s+2(n)log¿2 n). This improves the best known bound, and extends it to a more general class of objects.

U2 - 10.1007/s00454-007-9029-7

DO - 10.1007/s00454-007-9029-7

M3 - Article

SN - 0179-5376

VL - 40

SP - 127

EP - 140

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

Improved bounds on the union complexity of fat objects

Abstract

Access to Document

Fingerprint

Cite this