Halving balls in deterministic linear time

DOI10.1007/978-3-662-44777-2_47MaRDI QIDQ2921443zbMATH OpenOpenAlexFDO

Authors Vincent J. J. Kusters, Tillmann Miltzow

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.1894

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Abstract: Let $D$ be a set of $n$ pairwise disjoint unit balls in $R^d$ and $P$ the set of their center points. A hyperplane $Hy$ is an emph{$m$-separator} for $D$ if each closed halfspace bounded by $Hy$ 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 has been 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. We present three deterministic algorithms to bisect or approximately bisect a given set of disjoint unit balls by a hyperplane: Firstly, we present a simple linear-time algorithm to construct an $alphan$-separator for balls in $R^d$, for any $0<alpha<1/2$, that intersects at most $c{n}^{(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$ that intersects $O(n^{(5/6)+epsilon})$ disks. Our results improve the runtime of a disk sliding algorithm by Bereg, Dumitrescu and Pach. In addition, our results improve and derandomize an algorithm to construct a space decomposition used by L{"o}ffler and Mulzer to construct an onion (convex layer) decomposition for imprecise points (any point resides at an unknown location within a given disk).

Recommendations

• Halving balls by a hyperplane in deterministic linear time
• Balanced line separators of unit disk graphs
• Cutting a bunch of grapes by a plane
• Balanced line separators of unit disk graphs
• Algorithms for ham-sandwich cuts

Cited in

(4)

• Halving balls by a hyperplane in deterministic linear time
• scientific article; zbMATH DE number 741006 (Why is no real title available?)
• Balanced line separators of unit disk graphs
• Space-efficient algorithms for reachability in directed geometric graphs

This page was built for publication: Halving balls in deterministic linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921443)