Document Open Access Logo

Online Piercing of Geometric Objects

Authors Minati De , Saksham Jain, Sarat Varma Kallepalli, Satyam Singh

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.17.pdf
  • Filesize: 1.13 MB
  • 16 pages

Document Identifiers

Author Details

Minati De
  • Department of Mathematics, Indian Institute of Technology Delhi, New Delhi, India
Saksham Jain
  • Department of Mathematics, Indian Institute of Technology Delhi, New Delhi, India
Sarat Varma Kallepalli
  • Department of Mathematics, Indian Institute of Technology Delhi, New Delhi, India
Satyam Singh
  • Department of Mathematics, Indian Institute of Technology Delhi, New Delhi, India

Funding

Work on this paper by M. De has been partially supported by SERB MATRICS Grant MTR/2021/000584, and work by S. Singh has been supported by CSIR (File Number-09/086(1429)/2019-EMR_I).

Acknowledgements

Authors would like to acknowledge anonymous reviewers for giving constructive feedback that helped to improve the presentation of the paper.

Cite As Get BibTex

Minati De, Saksham Jain, Sarat Varma Kallepalli, and Satyam Singh. Online Piercing of Geometric Objects. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.17

Abstract

We consider the online version of the piercing set problem where geometric objects arrive one by one. The online algorithm must maintain a piercing set for the arrived objects by making irrevocable decisions. First, we show that any deterministic online algorithm that solves this problem has a competitive ratio of at least Ω(n), which even holds when the objects are one-dimensional intervals. On the other hand, piercing unit objects is equivalent to the unit covering problem which is well-studied in the online model. Due to this, all the results related to the online unit covering problem are preserved for the online unit piercing problem when the objects are translated from each other. Surprisingly, no upper bound was known for the unit covering problem when unit objects are anything other than balls and hypercubes. In this paper, we introduce the notion of α-aspect and α-aspect_∞ objects. We give an upper bound of competitive ratio for α-aspect and α-aspect_∞ objects in ℝ³ and ℝ^d, respectively, with a scaling factor in the range [1,k]. We also propose a lower bound of the competitive ratio for bounded scaled objects like α-aspect objects in ℝ², axis-aligned hypercubes in ℝ^d, and balls in ℝ² and ℝ³. For piercing α-aspect_∞ objects in ℝ^d, we show that a simple deterministic algorithm achieves a competitive ratio of at most (2/α)^d((1+α)^d-1) (⌈log_(1+α)(2k/α)⌉)+1. This result is very general in nature. One can obtain upper bounds for specific objects by specifying the value of α. By putting the value of k = 1 to the above result, we get an upper bound of the competitive ratio for the unit covering problem for various types of objects.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • piercing set problem
  • online algorithm
  • competitive ratio
  • unit covering problem
  • geometric objects

Metrics

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

Related Versions

References

  1. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM J. Comput., 39(2):361-370, 2009. URL: https://doi.org/10.1137/060661946.
  2. C. J. Argue, Anupam Gupta, Ziye Tang, and Guru Guruganesh. Chasing convex bodies with linear competitive ratio. J. ACM, 68(5):32:1-32:10, 2021. URL: https://doi.org/10.1145/3450349.
  3. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  4. Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing nested convex bodies nearly optimally. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1496-1508. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.91.
  5. Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Competitively chasing convex bodies. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 861-868. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316314.
  6. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms, 46(2):178-189, 2003. URL: https://doi.org/10.1016/S0196-6774(02)00294-8.
  7. Timothy M. Chan and Hamid Zarrabi-Zadeh. A randomized algorithm for online unit clustering. Theory Comput. Syst., 45(3):486-496, 2009. URL: https://doi.org/10.1007/s00224-007-9085-7.
  8. Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. SIAM J. Comput., 33(6):1417-1440, 2004. URL: https://doi.org/10.1137/S0097539702418498.
  9. Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth. Online unit covering in Euclidean space. Theor. Comput. Sci., 809:218-230, 2020. URL: https://doi.org/10.1016/j.tcs.2019.12.010.
  10. Adrian Dumitrescu and Csaba D. Tóth. Online unit clustering and unit covering in higher dimensions. Algorithmica, 84(5):1213-1231, 2022. URL: https://doi.org/10.1007/s00453-021-00916-6.
  11. Alon Efrat, Matthew J. Katz, Frank Nielsen, and Micha Sharir. Dynamic data structures for fat objects and their applications. Comput. Geom., 15(4):215-227, 2000. URL: https://doi.org/10.1016/S0925-7721(99)00059-0.
  12. Guy Even and Shakhar Smorodinsky. Hitting sets online and unique-max coloring. Discret. Appl. Math., 178:71-82, 2014. URL: https://doi.org/10.1016/j.dam.2014.06.019.
  13. Robert J. Fowler, Michael S. Paterson, and Steven L. Tanimoto. Optimal packing and covering in the plane are np-complete. Inf. Process. Lett., 12(3):133-137, 1981. URL: https://doi.org/10.1016/0020-0190(81)90111-3.
  14. Joel Friedman and Nathan Linial. On convex body chasing. Discret. Comput. Geom., 9:293-321, 1993. URL: https://doi.org/10.1007/BF02189324.
  15. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  16. J. W. Harris and H. Stocker. Handbook of Mathematics and Computational Science. New York: Springer-Verlag, 1998. Google Scholar
  17. Richard M. Karp. Reducibility among Combinatorial Problems, pages 85-103. Springer US, Boston, MA, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  18. Matthew J. Katz, Frank Nielsen, and Michael Segal. Maintenance of a piercing set for intervals with applications. Algorithmica, 36(1):59-73, 2003. URL: https://doi.org/10.1007/s00453-002-1006-1.
  19. Frank Nielsen. Fast stabbing of boxes in high dimensions. Theor. Comput. Sci., 246(1-2):53-72, 2000. URL: https://doi.org/10.1016/S0304-3975(98)00336-3.
  20. János Pach, Peter Brass, and William Moser. Research problems in discrete geometry. Research Problems in Discrete Geometry, January 2005. URL: https://doi.org/10.1007/0-387-29929-7.
  21. Mark Sellke. Chasing convex bodies optimally. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1509-1518. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.92.
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