Document Open Access Logo

Distant Representatives for Rectangles in the Plane

Authors Therese Biedl , Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, Graeme Stroud

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.17.pdf
  • Filesize: 1.84 MB
  • 18 pages

Document Identifiers

Author Details

Therese Biedl
  • David R. Cheriton School of Computer Science, University of Waterloo, Canada
Anna Lubiw
  • David R. Cheriton School of Computer Science, University of Waterloo, Canada
Anurag Murty Naredla
  • David R. Cheriton School of Computer Science, University of Waterloo, Canada
Peter Dominik Ralbovsky
  • David R. Cheriton School of Computer Science, University of Waterloo, Canada
Graeme Stroud
  • David R. Cheriton School of Computer Science, University of Waterloo, Canada

Funding

  • Biedl, Therese: Supported by NSERC.
  • Lubiw, Anna: Supported by NSERC.

Acknowledgements

We thank Jeffrey Shallit for help with continued fractions, and we thank anonymous reviewers for their helpful comments.

Cite AsGet BibTex

Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud. Distant Representatives for Rectangles in the Plane. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.17

Abstract

The input to the distant representatives problem is a set of n objects in the plane and the goal is to find a representative point from each object while maximizing the distance between the closest pair of points. When the objects are axis-aligned rectangles, we give polynomial time constant-factor approximation algorithms for the L₁, L₂, and L_∞ distance measures. We also prove lower bounds on the approximation factors that can be achieved in polynomial time (unless P = NP).

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Distant representatives
  • blocker shapes
  • matching
  • approximation algorithm
  • APX-hardness

Metrics

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

Related Versions

References

  1. Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. Framework for ∃ ℝ-completeness of two-dimensional packing problems. arXiv preprint arXiv:2004.07558, 2020. URL: https://arXiv.org/abs/2004.07558.
  2. Eric Bach and Jeffrey Shallit. Algorithmic Number Theory: Efficient Algorithms, volume 1. MIT press, 1996. Google Scholar
  3. Christoph Baur and Sándor P. Fekete. Approximation of geometric dispersion problems. Algorithmica, 30(3):451-470, 2001. URL: http://dx.doi.org/10.1007/s00453-001-0022-x.
  4. Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud. Dispersion for intervals: A geometric approach. In Symposium on Simplicity in Algorithms (SOSA), pages 37-44. SIAM, 2021. URL: http://dx.doi.org/10.1137/1.9781611976496.4.
  5. Sergio Cabello. Approximation algorithms for spreading points. Journal of Algorithms, 62(2):49-73, 2007. URL: http://dx.doi.org/10.1016/j.jalgor.2004.06.009.
  6. Jean Cardinal. Computational geometry column 62. ACM SIGACT News, 46(4):69-78, 2015. URL: http://dx.doi.org/10.1145/2852040.2852053.
  7. Erin Chambers, Alejandro Erickson, Sándor P. Fekete, Jonathan Lenchner, Jeff Sember, Venkatesh Srinivasan, Ulrike Stege, Svetlana Stolpner, Christophe Weibel, and Sue Whitesides. Connectivity graphs of uncertainty regions. Algorithmica, 78(3):990-1019, 2017. URL: http://dx.doi.org/10.1007/s00453-016-0191-2.
  8. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms, 46(2):178-189, 2003. Google Scholar
  9. Jing Chen, Bo Li, and Yingkai Li. Efficient approximations for the online dispersion problem. SIAM Journal on Computing, 48(2):373-416, 2019. URL: http://dx.doi.org/10.1137/17M1131027.
  10. Mark de Berg and Amirali Khosravi. Optimal binary space partitions in the plane. In International Computing and Combinatorics Conference, pages 216-225. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14031-0_25.
  11. Erik D. Demaine, Sándor P. Fekete, and Robert J. Lang. Circle packing for origami design is hard. arXiv preprint arXiv:1008.1224, 2010. URL: https://arxiv.org/abs/1008.1224.
  12. Srinivas Doddi, Madhav V. Marathe, Andy Mirzaian, Bernard M.E. Moret, and Binhai Zhou. Map labeling and its generalizations. In Proc. 8th Ann. ACM/SIAM Symp. Discrete Algs.(SODA97), pages 148-157. SIAM, 1997. Google Scholar
  13. Reza Dorrigiv, Robert Fraser, Meng He, Shahin Kamali, Akitoshi Kawamura, Alejandro López-Ortiz, and Diego Seco. On minimum-and maximum-weight minimum spanning trees with neighborhoods. Theory of Computing Systems, 56(1):220-250, 2015. URL: http://dx.doi.org/10.1007/s00224-014-9591-3.
  14. Adrian Dumitrescu and Minghui Jiang. Dispersion in disks. Theory of Computing Systems, 51(2):125-142, 2012. URL: http://dx.doi.org/10.1007/s00224-011-9331-x.
  15. Adrian Dumitrescu and Minghui Jiang. Systems of distant representatives in Euclidean space. Journal of Combinatorial Theory, Series A, 134:36-50, 2015. URL: http://dx.doi.org/10.1016/j.jcta.2015.03.006.
  16. Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow. Smoothing the gap between NP and ∃ ℝ. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1022-1033. IEEE, 2020. Google Scholar
  17. Jiří Fiala, Jan Kratochvíl, and Andrzej Proskurowski. Systems of distant representatives. Discrete Applied Mathematics, 145(2):306-316, 2005. URL: http://dx.doi.org/10.1016/j.dam.2004.02.018.
  18. Michael Formann and Frank Wagner. A packing problem with applications to lettering of maps. In Proceedings of the Seventh Annual Symposium on Computational Geometry, pages 281-288, 1991. Google Scholar
  19. Greg N. Frederickson and Donald B. Johnson. Generalized selection and ranking: sorted matrices. SIAM Journal on Computing, 13(1):14-30, 1984. Google Scholar
  20. Michael R. Garey, David S. Johnson, Barbara B. Simons, and Robert Endre Tarjan. Scheduling unit-time tasks with arbitrary release times and deadlines. SIAM Journal on Computing, 10(2):256-269, 1981. URL: http://dx.doi.org/10.1137/0210018.
  21. Philip Hall. On representatives of subsets. Journal of the London Mathematical Society, 1(1):26-30, 1935. Google Scholar
  22. Mhand Hifi and Rym M'hallah. A literature review on circle and sphere packing problems: Models and methodologies. Advances in Operations Research, 2009, 2009. URL: http://dx.doi.org/10.1155/2009/150624.
  23. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM (JACM), 32(1):130-136, 1985. URL: http://dx.doi.org/10.1016/j.orl.2010.07.004.
  24. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225-231, 1973. URL: http://dx.doi.org/10.1137/0202019.
  25. Joseph Y.T. Leung, Tommy W. Tam, Chin S. Wong, Gilbert H. Young, and Francis Y.L. Chin. Packing squares into a square. Journal of Parallel and Distributed Computing, 10(3):271-275, 1990. URL: http://dx.doi.org/10.1016/0743-7315(90)90019-L.
  26. Shimin Li and Haitao Wang. Dispersing points on intervals. Discrete Applied Mathematics, 239:106-118, 2018. URL: http://dx.doi.org/10.1016/j.dam.2017.12.028.
  27. Maarten Löffler and Marc van Kreveld. Largest and smallest convex hulls for imprecise points. Algorithmica, 56(2):235, 2010. URL: http://dx.doi.org/10.1007/s00453-008-9174-2.
  28. Maarten Löffler and Marc van Kreveld. Largest bounding box, smallest diameter, and related problems on imprecise points. Computational Geometry, 43(4):419-433, 2010. URL: http://dx.doi.org/10.1016/j.comgeo.2009.03.007.
  29. Roger J. Marshall. Scaled rectangle diagrams can be used to visualize clinical and epidemiological data. Journal of Clinical Epidemiology, 58(10):974-981, 2005. URL: http://dx.doi.org/10.1016/j.jclinepi.2005.01.018.
  30. M.J.M. Roeloffzen. Finding structures on imprecise points. Master’s thesis, TU Eindhoven, 2009. URL: https://www.win.tue.nl/~mroeloff/papers/thesis-roeloffzen2009.pdf.
  31. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, volume 24. Springer Science & Business Media, 2003. Google Scholar
  32. Barbara Simons. A fast algorithm for single processor scheduling. In 19th Annual Symposium on Foundations of Computer Science, pages 246-252. IEEE, 1978. URL: http://dx.doi.org/10.1109/SFCS.1978.4.
  33. Péter Gábor Szabó, Mihaly Csaba Markót, Tibor Csendes, Eckard Specht, Leocadio G. Casado, and Inmaculada García. New Approaches to Circle Packing in a Square: with Program Codes, volume 6. Springer Science & Business Media, 2007. Google Scholar
  34. Frank Wagner, Alexander Wolff, Vikas Kapoor, and Tycho Strijk. Three rules suffice for good label placement. Algorithmica, 30(2):334-349, 2001. Google Scholar
  35. Wikipedia contributors. Euclidean algorithm - Wikipedia, the free encyclopedia, 2021. [Online; accessed 28-June-2021]. URL: https://en.wikipedia.org/w/index.php?title=Euclidean_algorithm&oldid=1027503317.
  36. Alexander Wolff, Lars Knipping, Marc van Kreveld, Tycho Strijk, and Pankaj K. Agarwal. A simple and efficient algorithm for high-quality line labeling. In Peter Atkinson, editor, GIS and GeoComputation. Taylor and Francis, 2000. URL: http://dx.doi.org/10.1201/9781482268263.
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 Imprint Privacy Contact