On the union of κ-round objects in three and four dimensions

Boris Aronov; Alon Efrat; Vladlen Koltun; Micha Sharir

On the union of κ-round objects in three and four dimensions

Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

A compact body c in ℝ^d is κ-round if for every point p ∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ > 0, the combinatorial complexity of the union of n κ-round, not necessarily convex objects in ℝ³ (resp., in ℝ⁴) of constant description complexity is O(n^2+ε) (resp., O(n ^3+ε)) for any ε > 0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight.

Original language	English (US)
Title of host publication	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Pages	383-390
Number of pages	8
State	Published - 2004
Event	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004

Other

Other	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Country/Territory	United States
City	Brooklyn, NY
Period	6/9/04 → 6/11/04

Keywords

Combinatorial complexity
Fat objects
Union of objects

ASJC Scopus subject areas

Software
Geometry and Topology
Safety, Risk, Reliability and Quality
Chemical Health and Safety

Cite this

@inproceedings{a80233345b054edc9837ac3d49f8654f,

title = "On the union of κ-round objects in three and four dimensions",

abstract = "A compact body c in ℝd is κ-round if for every point p ∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ > 0, the combinatorial complexity of the union of n κ-round, not necessarily convex objects in ℝ3 (resp., in ℝ4) of constant description complexity is O(n2+ε) (resp., O(n 3+ε)) for any ε > 0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight.",

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

author = "Boris Aronov and Alon Efrat and Vladlen Koltun and Micha Sharir",

year = "2004",

language = "English (US)",

pages = "383--390",

booktitle = "Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)",

note = "Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) ; Conference date: 09-06-2004 Through 11-06-2004",

}

TY - GEN

T1 - On the union of κ-round objects in three and four dimensions

AU - Aronov, Boris

AU - Efrat, Alon

AU - Koltun, Vladlen

AU - Sharir, Micha

PY - 2004

Y1 - 2004

N2 - A compact body c in ℝd is κ-round if for every point p ∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ > 0, the combinatorial complexity of the union of n κ-round, not necessarily convex objects in ℝ3 (resp., in ℝ4) of constant description complexity is O(n2+ε) (resp., O(n 3+ε)) for any ε > 0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight.

AB - A compact body c in ℝd is κ-round if for every point p ∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ > 0, the combinatorial complexity of the union of n κ-round, not necessarily convex objects in ℝ3 (resp., in ℝ4) of constant description complexity is O(n2+ε) (resp., O(n 3+ε)) for any ε > 0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight.

KW - Combinatorial complexity

KW - Fat objects

KW - Union of objects

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

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

M3 - Conference contribution

AN - SCOPUS:4544224037

SP - 383

EP - 390

BT - Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)

T2 - Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)

Y2 - 9 June 2004 through 11 June 2004

ER -

On the union of κ-round objects in three and four dimensions

Abstract

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this