dc.contributor.author
Hoffmann, Michael
dc.contributor.author
Kusters, Vincent
dc.contributor.author
Miltzow, Tillmann
dc.date.accessioned
2021-08-12T11:31:16Z
dc.date.available
2021-07-15T10:47:15Z
dc.date.available
2021-08-11T06:52:26Z
dc.date.available
2021-08-12T11:31:16Z
dc.date.issued
2020-03
dc.identifier.issn
1920-180X
dc.identifier.other
10.20382/jocg.v11i1a23
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/495120
dc.identifier.doi
10.3929/ethz-b-000495120
dc.description.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.
en_US
dc.description.abstract
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.
en_US
dc.description.abstract
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).
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Carleton University
en_US
dc.rights.uri
dc.title
Halving balls by a hyperplane in deterministic linear time
en_US
dc.type
Journal Article
dc.date.published
2020-12-14
ethz.journal.title
Journal of Computational Geometry
ethz.journal.volume
11
en_US
ethz.journal.issue
1
en_US
ethz.pages.start
576
en_US
ethz.pages.end
614
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.grant
Arrangements and Drawings (ArrDra)
en_US
ethz.identifier.wos
ethz.publication.place
Ottawa
en_US
ethz.publication.status
published
en_US
ethz.grant.agreementno
171681
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
Projekte MINT
ethz.date.deposited
2021-07-15T10:47:37Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2021-08-11T06:52:36Z
ethz.rosetta.lastUpdated
2022-03-29T11:02:10Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.atitle=Halving%20balls%20by%20a%20hyperplane%20in%20deterministic%20linear%20time&amp;rft.jtitle=Journal%20of%20Computational%20Geometry&amp;rft.date=2020-03&amp;rft.volume=11&amp;rft.issue=1&amp;rft.spage=576&amp;rft.epage=614&amp;rft.issn=1920-180X&amp;rft.au=Hoffmann,%20Michael&amp;Kusters,%20Vincent&amp;Miltzow,%20Tillmann&amp;rft.genre=article&amp;rft_id=info:doi/10.20382/jocg.v11i1a23&amp;
﻿ Search print copy at ETH Library