On the complexity of the union of fat objects in the plane

Alon Efrat; Micha Sharir

doi:10.1145/262839.262911

On the complexity of the union of fat objects in the plane

Alon Efrat, Micha Sharir

Computer Science

Research output: Contribution to conference › Paper › peer-review

19 Scopus citations

Abstract

We prove a near-linear bound on the combinatorial complexity of the union of n fat convex objects in the plane, each pair of whose boundaries cross at most a constant number of times.

Original language	English (US)
Pages	104-112
Number of pages	9
DOIs	https://doi.org/10.1145/262839.262911
State	Published - 1997
Event	Proceedings of the 1997 13th Annual Symposium on Computational Geometry - Nice, Fr Duration: Jun 4 1997 → Jun 6 1997

Other

Other	Proceedings of the 1997 13th Annual Symposium on Computational Geometry
City	Nice, Fr
Period	6/4/97 → 6/6/97

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/262839.262911

Cite this

@conference{c8c21140f81c4e71b06e556aae789ff2,

title = "On the complexity of the union of fat objects in the plane",

abstract = "We prove a near-linear bound on the combinatorial complexity of the union of n fat convex objects in the plane, each pair of whose boundaries cross at most a constant number of times.",

author = "Alon Efrat and Micha Sharir",

year = "1997",

doi = "10.1145/262839.262911",

language = "English (US)",

pages = "104--112",

note = "Proceedings of the 1997 13th Annual Symposium on Computational Geometry ; Conference date: 04-06-1997 Through 06-06-1997",

}

TY - CONF

T1 - On the complexity of the union of fat objects in the plane

AU - Efrat, Alon

AU - Sharir, Micha

PY - 1997

Y1 - 1997

N2 - We prove a near-linear bound on the combinatorial complexity of the union of n fat convex objects in the plane, each pair of whose boundaries cross at most a constant number of times.

AB - We prove a near-linear bound on the combinatorial complexity of the union of n fat convex objects in the plane, each pair of whose boundaries cross at most a constant number of times.

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

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

U2 - 10.1145/262839.262911

DO - 10.1145/262839.262911

M3 - Paper

SP - 104

EP - 112

T2 - Proceedings of the 1997 13th Annual Symposium on Computational Geometry

Y2 - 4 June 1997 through 6 June 1997

ER -

On the complexity of the union of fat objects in the plane

Abstract

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this