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: Contribution to conference › Paper › peer-review

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)
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

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Cite this

@conference{8a522f76fb79419e98bd1ea233a73697,

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",

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

}

TY - CONF

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 - https://www.scopus.com/pages/publications/4544224037

UR - https://www.scopus.com/pages/publications/4544224037#tab=citedBy

M3 - Paper

AN - SCOPUS:4544224037

SP - 383

EP - 390

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