Document Open Access Logo

Some Open Problems in Computational Geometry (Invited Talk)

Author Sergio Cabello

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.2.pdf
  • Filesize: 469 kB
  • 6 pages

Document Identifiers

Author Details

Sergio Cabello
  • University of Ljubljana, Slovenia
  • Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

Funding

Supported by the Slovenian Research Agency, program P1-0297 and projects J1-1693, J1-9109.

Cite As Get BibTex

Sergio Cabello. Some Open Problems in Computational Geometry (Invited Talk). In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 2:1-2:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.2

Abstract

In this paper we shall encounter three open problems in Computational Geometry that are, in my opinion, interesting for a general audience interested in algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • barrier resilience
  • maximum matching
  • geometric graphs
  • fixed-parameter tractability
  • stochastic computational geometry

Metrics

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

References

  1. Helmut Alt, Sergio Cabello, Panos Giannopoulos, and Christian Knauer. Minimum cell connection in line segment arrangements. Int. J. Comput. Geom. Appl., 27(3):159-176, 2017. URL: https://doi.org/10.1142/S0218195917500017.
  2. Édouard Bonnet, Sergio Cabello, and Wolfgang Mulzer. Maximum matchings in geometric intersection graphs. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, pages 31:1-31:17, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.31.
  3. Sergio Cabello and Éric Colin de Verdière. Hardness of minimum barrier shrinkage and minimum installation path. Theoretical Computer Science, in print. URL: https://doi.org/10.1016/j.tcs.2020.06.016.
  4. Sergio Cabello, Kshitij Jain, Anna Lubiw, and Debajyoti Mondal. Minimum shared-power edge cut. Networks, 75(3):321-333, 2020. URL: https://doi.org/10.1002/net.21928.
  5. Sergio Cabello and Wolfgang Mulzer. Minimum cuts in geometric intersection graphs. CoRR, abs/2005.00858, 2020. URL: https://arxiv.org/abs/2005.00858.
  6. Timothy M. Chan. Klee’s measure problem made easy. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, pages 410-419, 2013. URL: https://doi.org/10.1109/FOCS.2013.51.
  7. Bernard Chazelle and Herbert Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. ACM, 39(1):1-54, 1992. URL: https://doi.org/10.1145/147508.147511.
  8. Herbert Edelsbrunner and John Harer. Computational Topology - an Introduction. American Mathematical Society, 2010. URL: http://www.ams.org/bookstore-getitem/item=MBK-69.
  9. Alon Efrat, Alon Itai, and Matthew J. Katz. Geometry helps in bottleneck matching and related problems. Algorithmica, 31(1):1-28, 2001. URL: https://doi.org/10.1007/s00453-001-0016-8.
  10. Pegah Kamousi, Timothy M. Chan, and Subhash Suri. Stochastic minimum spanning trees in euclidean spaces. In Proceedings of the 27th ACM Symposium on Computational Geometry, (SoCG 2011), pages 65-74, 2011. URL: https://doi.org/10.1145/1998196.1998206.
  11. Pegah Kamousi, Timothy M. Chan, and Subhash Suri. Closest pair and the post office problem for stochastic points. Comput. Geom., 47(2):214-223, 2014. URL: https://doi.org/10.1016/j.comgeo.2012.10.010.
  12. Matias Korman, Maarten Löffler, Rodrigo I. Silveira, and Darren Strash. On the complexity of barrier resilience for fat regions and bounded ply. Comput. Geom., 72:34-51, 2018. URL: https://doi.org/10.1016/j.comgeo.2018.02.006.
  13. Santosh Kumar, Ten-Hwang Lai, and Anish Arora. Barrier coverage with wireless sensors. Wirel. Networks, 13(6):817-834, 2007. URL: https://doi.org/10.1007/s11276-006-9856-0.
  14. Jiří Matoušek. Range searching with efficient hiearchical cutting. Discret. Comput. Geom., 10:157-182, 1993. URL: https://doi.org/10.1007/BF02573972.
  15. Marcin Mucha and Piotr Sankowski. Maximum matchings in planar graphs via gaussian elimination. Algorithmica, 45(1):3-20, 2006. URL: https://doi.org/10.1007/s00453-005-1187-5.
  16. Franco P. Preparata and Michael I. Shamos. Computational Geometry - An Introduction. Texts and Monographs in Computer Science. Springer, 1985. URL: https://doi.org/10.1007/978-1-4612-1098-6.
  17. Michael O. Rabin. Probabilistic algorithms. In Algorithms and Complexity: New Directions and Recent Results. Academic Press, 1976. Google Scholar
  18. Kuan-Chieh Robert Tseng and David G. Kirkpatrick. On barrier resilience of sensor networks. In Algorithms for Sensor Systems - 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2011, volume 7111 of Lecture Notes in Computer Science, pages 130-144. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-28209-6_11.
  19. Constantinos Tsirogiannis, Frank Staals, and Vincent Pellissier. Computing the expected value and variance of geometric measures. ACM J. Exp. Algorithmics, 23, 2018. URL: https://doi.org/10.1145/3228331.
  20. Salil P. Vadhan. The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput., 31(2):398-427, 2001. URL: https://doi.org/10.1137/S0097539797321602.
  21. Raphael Yuster and Uri Zwick. Maximum matching in graphs with an excluded minor. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pages 108-117, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283396.
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