
Open access
Date
2020-03Type
- Journal Article
ETH Bibliography
yes
Altmetrics
Abstract
Let D be a set of n pairwise disjoint unit balls in R-d and P the set of their centers. A hyperplane H is an m-separator for D if every closed halfspace bounded by H contains at least m points from P. This generalizes the notion of halving hyperplanes, which correspond to n/2-separators. The analogous notion for point sets is well studied. Separators have various applications, for instance, in divide-and-conquer schemes. In such a scheme, any ball that is intersected by the separating hyperplane may still interact with both sides of the partition. Therefore it is desirable that the separating hyperplane intersects a small number of balls only. Show more
We present three deterministic algorithms to bisect a given set of pairwise disjoint unit balls by a hyperplane. Firstly, we present a simple linear-time algorithm to construct an alpha n-separator for balls in R-d, for any 0 < alpha < 1/2, that intersects at most cn((d-1)/d) balls, for some constant c that depends on d and alpha. The number of intersected balls is best possible up to the constant c. Secondly, we present a near-linear-time algorithm to construct an (n/2 - o(n))-separator in R-d that intersects o(n) balls. Finally, we give a linear-time algorithm to construct a halving line in R-2 for P that intersects O(n((2=3)+epsilon)) disks. Show more
We also point out how the above theorems can be generalized to more general classes of shapes, possibly with some overlap, and what are the limits of those generalizations. Our results improve the runtime of a disk sliding algorithm by Bereg, Dumitrescu and Pach. In addition, our results simplify and derandomize an algorithm to construct a space decomposition used by Loffler and Mulzer to construct an onion (convex layer) decomposition for imprecise points (any point resides at an unknown location within a given disk). Show more
Permanent link
https://doi.org/10.3929/ethz-b-000495120Publication status
publishedExternal links
Journal / series
Journal of Computational GeometryVolume
Pages / Article No.
Publisher
Carleton UniversityFunding
171681 - Arrangements and Drawings (ArrDra) (SNF)
More
Show all metadata
ETH Bibliography
yes
Altmetrics