Document Open Access Logo

Separating a Voronoi Diagram via Local Search

Authors Vijay V. S. P. Bhattiprolu, Sariel Har-Peled

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.18.pdf
  • Filesize: 0.79 MB
  • 16 pages

Document Identifiers

Author Details

Vijay V. S. P. Bhattiprolu
Sariel Har-Peled

Cite As Get BibTex

Vijay V. S. P. Bhattiprolu and Sariel Har-Peled. Separating a Voronoi Diagram via Local Search. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.18

Abstract

Given a set P of n points in R^d , we show how to insert a set Z of  O(n^(1-1/d)) additional points, such that P can be broken into two sets P1 and P2 , of roughly equal size, such that in the Voronoi diagram V(P u Z), the cells of P1 do not touch the cells of P2; that is, Z separates P1 from P2 in the Voronoi diagram (and also in the dual Delaunay triangulation). In addition, given such a partition (P1,P2) of P , we present an approximation algorithm to compute a minimum size separator realizing this partition. We also present a simple local search algorithm that is a PTAS for approximating the optimal Voronoi partition.

Subject Classification

Keywords
  • Separators
  • Local search
  • Approximation
  • Voronoi diagrams
  • Delaunay triangulation
  • Meshing
  • Geometric hitting set

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Alon, P. Seymour, and R. Thomas. A separator theorem for nonplanar graphs. In J. Amer. Math. Soc., volume 3, pages 801-808, 1990. URL: http://dx.doi.org/10.1090/S0894-0347-1990-1065053-0.
  2. V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544-562, 2004. URL: http://dx.doi.org/10.1137/S0097539702416402.
  3. F. Aurenhammer, R. Klein, and D.-T. Lee. Voronoi Diagrams and Delaunay Triangulations. World Scientific, 2013. URL: http://dx.doi.org/10.1142/8685.
  4. S. Bandyapadhyay and K. R. Varadarajan. On variants of k-means clustering. CoRR, abs/1512.02985, 2015. Also in SoCG 16. URL: http://arxiv.org/abs/1512.02985.
  5. S. Basu, R. Pollack, and M. F. Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, 2006. URL: http://dx.doi.org/10.1007/3-540-33099-2.
  6. M. de Berg, O. Cheong, M. van Kreveld, and M. H. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, Santa Clara, CA, USA, 3rd edition, 2008. URL: http://www.cs.uu.nl/geobook/.
  7. V. V. S. P. Bhattiprolu and S. Har-Peled. Separating a voronoi diagram via local search. CoRR, abs/1401.0174, 2014. URL: http://arxiv.org/abs/1401.0174.
  8. J. Böttcher, K. P. Pruessmann, A. Taraz, and A. Würfl. Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs. Eur. J. Comb., 31(5):1217-1227, July 2010. URL: http://dx.doi.org/10.1016/j.ejc.2009.10.010.
  9. T. M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms, 46(2):178-189, 2003. URL: http://dx.doi.org/10.1016/S0196-6774(02)00294-8.
  10. T. M. Chan and S. Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput. Geom., 48:373-392, 2012. URL: http://dx.doi.org/10.1007/s00454-012-9417-5.
  11. Z. Dvorak and S. Norin. Strongly sublinear separators and polynomial expansion. ArXiv e-prints, April 2015. URL: http://arxiv.org/abs/1504.04821,
  12. A. Efrat and S. Har-Peled. Guarding galleries and terrains. Inform. Process. Lett., 100(6):238-245, 2006. URL: http://dx.doi.org/10.1016/j.ipl.2006.05.014.
  13. D. Eisenstat and P. N. Klein. Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. In Proc. 45th Annu. ACM Sympos. Theory Comput. (STOC), pages 735-744, 2013. URL: http://dx.doi.org/10.1145/2488608.2488702.
  14. T. Erlebach, K. Jansen, and E. Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput., 34(6):1302-1323, 2005. URL: http://dx.doi.org/10.1137/S0097539702402676.
  15. J. Fakcharoenphol and S. Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Sys. Sci., 72(5):868-889, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2005.05.007.
  16. J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan. A separator theorem for graphs of bounded genus. J. Algorithms, 5(3):391-407, 1984. URL: http://dx.doi.org/10.1016/0196-6774(84)90019-1.
  17. A. Gupta and K. Tangwongsan. Simpler analyses of local search algorithms for facility location. ArXiv e-prints, September 2008. URL: http://arxiv.org/abs/0809.2554,
  18. S. Har-Peled. Geometric Approximation Algorithms, volume 173 of Mathematical Surveys and Monographs. Amer. Math. Soc., Boston, MA, USA, 2011. URL: http://sarielhp.org/book/, URL: http://dx.doi.org/10.1090/surv/173.
  19. S. Har-Peled. A simple proof of the existence of a planar separator. ArXiv e-prints, 2011. URL: http://arxiv.org/abs/1105.0103,
  20. S. Har-Peled and M. Lee. Weighted geometric set cover problems revisited. J. Comput. Geom., 3(1):65-85, 2012. URL: http://sarielhp.org/papers/08/expand_cover/.
  21. S. Har-Peled and K. Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. In Proc. 23nd Annu. Euro. Sympos. Alg.\CNFESA, volume 9294 of Lect. Notes in Comp. Sci., pages 717-728, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_60.
  22. P. N. Klein. A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput., 37(6):1926-1952, 2008. URL: http://dx.doi.org/10.1137/060649562.
  23. P. Koebe. Kontaktprobleme der konformen Abbildung. Ber. Verh. Sächs. Akademie der Wissenschaften Leipzig, Math.-Phys. Klasse, 88:141-164, 1936. Google Scholar
  24. R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36:177-189, 1979. URL: http://dx.doi.org/10.1137/0136016.
  25. R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615-627, 1980. URL: http://dx.doi.org/10.1137/0209046.
  26. G. L. Miller, S. H. Teng, W. P. Thurston, and S. A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. Assoc. Comput. Mach., 44(1):1-29, 1997. URL: http://dx.doi.org/10.1145/256292.256294.
  27. N. H. Mustafa, R. Raman, and S. Ray. Settling the APX-hardness status for geometric set cover. In Proc. 55th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 541-550, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.64.
  28. N. H. Mustafa and S. Ray. Improved results on geometric hitting set problems. Discrete Comput. Geom., 44(4):883-895, 2010. URL: http://dx.doi.org/10.1007/s00454-010-9285-9.
  29. J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion I. decompositions. Eur. J. Comb., 29(3):760-776, 2008. Google Scholar
  30. J. O'Rourke. Art Gallery Theorems and Algorithms. The International Series of Monographs on Computer Science. Oxford University Press, 1987. URL: http://cs.smith.edu/~orourke/books/art.html.
  31. J. Pach and P. K. Agarwal. Combinatorial Geometry. John Wiley &Sons, 1995. URL: http://www.addall.com/Browse/Detail/0471588903.html.
  32. W. D. Smith and N. C. Wormald. Geometric separator theorems and applications. In Proc. 39th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 232-243, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743449.
  33. C. Sommer, E. Verbin, and W. Yu. Distance oracles for sparse graphs. In Proc. 50th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 703-712, Georgia, USA, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.27.
  34. P. Ungar. A theorem on planar graphs. J. London Math. Soc., 26:256-262, 1951. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact