Document Open Access Logo

Planar Support for Non-piercing Regions and Applications

Authors Rajiv Raman, Saurabh Ray

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.69.pdf
  • Filesize: 0.65 MB
  • 14 pages

Document Identifiers

Author Details

Rajiv Raman
  • IIIT-Delhi, Delhi, India
Saurabh Ray
  • Department of Computer Science, NYU Abu Dhabi, United Arab Emirates

Cite As Get BibTex

Rajiv Raman and Saurabh Ray. Planar Support for Non-piercing Regions and Applications. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.69

Abstract

Given a hypergraph H=(X,S), a planar support for H is a planar graph G with vertex set X, such that for each hyperedge S in S, the sub-graph of G induced by the vertices in S is connected. Planar supports for hypergraphs have found several algorithmic applications, including several packing and covering problems, hypergraph coloring, and in hypergraph visualization.
The main result proved in this paper is the following: given two families of regions R and B in the plane, each of which consists of connected, non-piercing regions, the intersection hypergraph H_R(B) = (B, {B_r}_{r in R}), where B_r = {b in B: b cap r != empty set} has a planar support. Further, such a planar support can be computed in time polynomial in |R|, |B|, and the number of vertices in the arrangement of the regions in R cup B. Special cases of this result include the setting where either the family R, or the family B is a set of points.
Our result unifies and generalizes several previous results on planar supports, PTASs for packing and covering problems on non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
Keywords
  • Geometric optimization
  • packing and covering
  • non-piercing regions

Metrics

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

References

  1. Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray. Packing and covering with non-piercing regions. Discrete & Computational Geometry, Mar 2018. URL: http://dx.doi.org/10.1007/s00454-018-9983-2.
  2. Kevin Buchin, Marc Van Kreveld, Henk Meijer, Bettina Speckmann, and Kevin Verbeek. On planar supports for hypergraphs. In International Symposium on Graph Drawing, pages 345-356. Springer, 2009. Google Scholar
  3. Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 1576-1585, 2012. Google Scholar
  4. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373-392, 2012. Google Scholar
  5. Kenneth L Clarkson and Peter W Shor. Applications of random sampling in computational geometry, ii. Discrete &Computational Geometry, 4(5):387-421, 1989. Google Scholar
  6. Alina Ene, Sariel Har-Peled, and Benjamin Raichel. Geometric packing under non-uniform constraints. In Proceedings of the Twenty-eighth Annual Symposium on Computational Geometry, SoCG '12, pages 11-20, New York, NY, USA, 2012. ACM. Google Scholar
  7. Matt Gibson and Imran A. Pirwani. Algorithms for dominating set in disk graphs: Breaking the log n barrier. In Algorithms - ESA 2010 - 18th Annual European Symposium, Liverpool, United Kingdom, September 6-8, 2010, Proceedings, pages 243-254, 2010. Google Scholar
  8. David S Johnson and Henry O Pollak. Hypergraph planarity and the complexity of drawing venn diagrams. Journal of graph theory, 11(3):309-325, 1987. Google Scholar
  9. Chaya Keller and Shakhar Smorodinsky. Conflict-free coloring of intersection graphs of geometric objects. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2397-2411, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.154.
  10. Balázs Keszegh. Coloring intersection hypergraphs of pseudo-disks. In Proceedings of the Thirty-fourth International Symposium on Computational Geometry, 2018. URL: http://arxiv.org/abs/1711.05473.
  11. Nabil H. Mustafa, Rajiv Raman, and Saurabh Ray. Quasi-polynomial time approximation scheme for weighted geometric set cover on pseudodisks and halfspaces. SIAM Journal on Computing, 44(6):1650-1669, 2015. Google Scholar
  12. Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010. Google Scholar
  13. Evangelia Pyrga and Saurabh Ray. New existence proofs for ε-nets. In Proceedings of the Twenty-fourth Annual Symposium on Computational Geometry, SoCG '08, pages 199-207, New York, NY, USA, 2008. ACM. Google Scholar
  14. Kasturi Varadarajan. Weighted geometric set cover via quasi-uniform sampling. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 641-648, 2010. 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