On the Union of κ-Round Objects in Three and Four Dimensions

Boris Aronov, Alon Efrat, Vladlen Koltun and Micha Sharir
Discrete and Computational Geometry
Volume 36, Number 4 / December, 2006
Pages 511-526
http://dx.doi.org/10.1007/s00454-006-1263-x

SoCG2004の特集号から．

3次元と4次元の幾何的対象の合併の複雑さに関する研究．
幾何的対象としてはκ-round objectというものを扱っている．
これは「球のような対象」ということである．
d次元の対象Oがκ-roundであることの定義は，Oの境界上にある任意の点pに対して，
半径κのd次元球で，pを含み，Oに含まれるものが存在することである．
ただし，Oが対象 (object) であるとは内部が空でないコンパクト連結集合とする．
κ-round objectは凸である必要がないところも面白い．

この定義において，3次元のn個のκ-round objectsの合併の複雑さがO(n^{2+ε})であり，
4次元の場合はO(n^{3+ε})であることが示されている．ただし，εは任意の定数であり，
オーダー記法が隠す定数はκとε，および対象の代数的複雑さに依存する．
この上界がほとんどタイトであることを示す下界の構成法も与えられている．