Fetching the paper…
Reading the bibliography…
Given a set $\mathsf{P}$ of $n$ points in $\mathbb{R}^d$, we show how to insert a set $\mathsf{X}$ of $O( n^{1-1/d} )$ additional points, such that $\mathsf{P}$ can be broken into two sets $\mathsf{P}_1$ and $\mathsf{P}_2$, of roughly equal size, such that in the Voronoi diagram $\mathcal{V}( \mathsf{P} \cup \mathsf{X} )$, the cells of $\mathsf{P}_1$ do not touch the cells of $\mathsf{P}_2$; that is, $\mathsf{X}$ separates $\mathsf{P}_1$ from $\mathsf{P}_2$ in the Voronoi diagram.
Kontaktprobleme der konformen Abbildung
P. Koebe · 1936
Earlier work this paper cites.
A separator theorem for planar graphs
R. J. Lipton and R. E. Tarjan · 1977
Earlier work this paper cites.
A separator theorem for planar graphs
R. J. Lipton and R. E. Tarjan · 1979
Earlier work this paper cites.
A separator theorem for graphs of bounded genus
J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan · 1984
Earlier work this paper cites.
Art Gallery Theorems and Algorithms
J. O’Rourke · 1987
Earlier work this paper cites.
A separator theorem for graphs with an excluded minor and its applications
N. Alon , P. D. Seymour, and R. Thomas · 1990
Earlier work this paper cites.
Combinatorial Geometry
J. Pach and P. K. Agarwal · 1995
Earlier work this paper cites.
Separators for sphere-packings and nearest neighbor graphs
G. L. Miller, S. H. Teng, W. P. Thurston, and S. A. Vavasis · 1997
Earlier work this paper cites.
Geometric separator theorems and applications
W. D. Smith and N. C. Wormald · 1998
Earlier work this paper cites.
Local search heuristic for k k -median and facility location problems
V. Arya, N. Garg, R. Khandekar, K. Munagala, and V. Pandit · 2001
Earlier work this paper cites.
Polynomial-time approximation schemes for packing and piercing fat objects
T. M. Chan · 2003
Cited alongside, same era.
Polynomial-time approximation schemes for geometric intersection graphs
T. Erlebach, K. Jansen, and E. Seidel · 2005
Cited alongside, same era.
Fast algorithms for computing the smallest k k -enclosing disc
S. Har-Peled and S. Mazumdar · 2005
Cited alongside, same era.
Algorithms in Real Algebraic Geometry
S. Basu, R. Pollack, and M. F. Roy · 2006
Cited alongside, same era.
Guarding galleries and terrains
A. Efrat and S. Har-Peled · 2006
Cited alongside, same era.
Planar graphs, negative weight edges, shortest paths, and near linear time
J. Fakcharoenphol and S. Rao · 2006
Cited alongside, same era.
PTAS for geometric hitting set problems via local search
N. H. Mustafa and S. Ray · 2009
Later among the works it cites.
Distance oracles for sparse graphs
C. Sommer, E. Verbin, and W. Yu · 2009
Later among the works it cites.
Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
J. Böttcher, K. P. Pruessmann, A. Taraz, and A. Würfl · 2010
Later among the works it cites.
Geometric Approximation Algorithms
S. Har-Peled · 2011
Later among the works it cites.
A simple proof of the existence of a planar separator
S. Har-Peled · 2011
Later among the works it cites.
Approximation algorithms for maximum independent set of pseudo-disks
T. M. Chan and S. Har-Peled · 2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Computational Geometry: Algorithms and Applications
M. de Berg, O. Cheong , M. van Kreveld, and M. H. Overmars · 2008
Cited alongside, same era.
Simpler analyses of local search algorithms for facility location
A. Gupta and K. Tangwongsan · 2008
Cited alongside, same era.
A linear-time approximation scheme for tsp in undirected planar graphs with edge-weights
P. N. Klein · 2008
Cited alongside, same era.
Weighted geometric set cover problems revisited
S. Har-Peled and M. Lee · 2012
Later among the works it cites.
Voronoi Diagrams and Delaunay Triangulations
F. Aurenhammer, R. Klein, and D.-T. Lee · 2013
Closest in time.
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
D. Eisenstat and P. N. Klein · 2013
Closest in time.