Document Open Access Logo

Cutting Polygons into Small Pieces with Chords: Laser-Based Localization

Authors Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, Csaba D. Tóth

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.7.pdf
  • Filesize: 0.9 MB
  • 23 pages

Document Identifiers

Author Details

Esther M. Arkin
  • Stony Brook University, NY, USA
Rathish Das
  • Stony Brook University, NY, USA
Jie Gao
  • Rutgers University, Piscataway, NJ, USA
Mayank Goswami
  • Queens College of CUNY, New York, NY, USA
Joseph S. B. Mitchell
  • Stony Brook University, NY, USA
Valentin Polishchuk
  • Linköping University, Norrköping, Sweden
Csaba D. Tóth
  • California State University Northridge, Los Angeles, CA, USA
  • Tufts University, Medford, MA, USA

Funding

This research was partially supported by NSF grants CCF-1439084, CCF-1540890, CCF-1617618, CCF-1716252, CCF-1725543, CCF-1910873, CCF-2007275, CNS-1618391, CNS-1938709, CRII-1755791, CSR-1763680, DMS-1737812, DMS-1800734, and OAC-1939459. The authors also acknowledge partial support from the US-Israel Binational Science Foundation (project 2016116), the DARPA Lagrange program, the Sandia National Labs and grants by the Swedish Transport Administration and the Swedish Research Council.

Acknowledgements

We thank Peter Brass for technical discussions and for organizing an NSF-funded workshop where these problems were discussed and this collaboration began.

Cite AsGet BibTex

Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth. Cutting Polygons into Small Pieces with Chords: Laser-Based Localization. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.7

Abstract

Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into small-size pieces, using the chords of the polygon. Several versions are considered, depending on the definition of the "size" of a piece. In particular, we consider the area, the diameter, and the radius of the largest inscribed circle as a measure of the size of a piece. We also consider different objectives, either minimizing the maximum size of a piece for a given number of chords, or minimizing the number of chords that achieve a given size threshold for the pieces. We give hardness results for polygons with holes and approximation algorithms for multiple variants of the problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Packing and covering problems
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Computational geometry
Keywords
  • Polygon partition
  • Arrangements
  • Visibility
  • Localization

Metrics

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

Related Versions

References

  1. Bogdan Armaselu and Ovidiu Daescu. Algorithms for fair partitioning of convex polygons. Theoretical Computer Science, 607:351-362, 2015. URL: https://doi.org/10.1016/j.tcs.2015.08.003.
  2. Imre Bárány, Pavle Blagojević, and András Szűcs. Equipartitioning by a convex 3-fan. Advances in Mathematics, 223(2):579-593, 2010. URL: https://doi.org/10.1016/j.aim.2009.08.016.
  3. Aandrás Bezdek and Károly Bezdek. A solution of Conway’s fried potato problem. Bulletin of the London Mathematical Society, 27(5):492-496, 1995. URL: https://doi.org/10.1112/blms/27.5.492.
  4. Pavle V. M. Blagojević and Günter M. Ziegler. Convex equipartitions via equivariant obstruction theory. Israel Journal of Mathematics, 200(1):49-77, 2014. URL: https://doi.org/10.1007/s11856-014-1006-6.
  5. Karol Borsuk. Drei Sätze über die n-dimensionale euklidische Sphäre. Fundamenta Mathematicae, 20:177-190, 1933. URL: https://doi.org/10.4064/fm-20-1-177-190.
  6. Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, and Anil Maheshwari. Polygon cutting: Revisited. In Proc. Japanese Conference on Discrete and Computational Geometry (JCDCG), volume 1763 of LNCS, pages 81-92. Springer, 1998. URL: https://doi.org/10.1007/978-3-540-46515-7_7.
  7. Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete and Computational Geometry, 14(4):463-479, 1995. URL: https://doi.org/10.1007/BF02570718.
  8. Bernard Chazelle. A theorem on polygon cutting with applications. In Proc. 23rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 339-349, 1982. URL: https://doi.org/10.1109/SFCS.1982.58.
  9. Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy. Unsolved Problems in Geometry. Springer-Verlag, New York, 1991. URL: https://doi.org/10.1007/978-1-4612-0963-8.
  10. Gautam Das and Giri Narasimhan. Geometric searching and link distance. In Proc. 2nd Workshop on Algorithms and Data Structures (WADS), volume 519 of LNCS, pages 261-272. Springer, 1991. URL: https://doi.org/10.1007/BFb0028268.
  11. Robert Freimer, Joseph S. B. Mitchell, and Christine Piatko. On the complexity of shattering using arrangements. Technical report, Cornell University, 1991. Google Scholar
  12. Unnikrishnan Gopinathan, David J. Brady, and Nikos Pitsianis. Coded apertures for efficient pyroelectric motion tracking. Opt. Express, 11(18):2142-2152, 2003. URL: https://doi.org/10.1364/OE.11.002142.
  13. Roser Guàrdia and Ferran Hurtado. On the equipartition of plane convex bodies and convex polygons. Journal of Geometry, 83(1):32-45, 2005. URL: https://doi.org/10.1007/s00022-005-0006-0.
  14. Steven C. Gustafson. Intensity correlation techniques for passive optical device detection. In Infrared Technology for Target Detection and Classification, volume 302, pages 66-70. International Society for Optics and Photonics, SPIE, 1982. URL: https://doi.org/10.1117/12.932632.
  15. Refael Hassin and Nimrod Megiddo. Approximation algorithms for hitting objects with straight lines. Discrete Applied Mathematics, 30(1):29-42, 1991. URL: https://doi.org/10.1016/0166-218X(91)90011-K.
  16. Tian He, Qiuhua Cao, Liqian Luo, Ting Yan, Lin Gu, John Stankovic, and Tarek Abdelzaher. Electronic tripwires for power-efficient surveillance and target classification. In Proc. 2nd International Conference on Embedded Networked Sensor Systems (SenSys 2004). ACM Press, 2004. URL: https://doi.org/10.1145/1031495.1031558.
  17. John Hershberger and Subhash Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. J. Algorithms, 18(3):403-431, 1995. URL: https://doi.org/10.1006/jagm.1995.1017.
  18. Thomas Jenrich and Andries E. Brouwer. A 64-dimensional counterexample to Borsuk’s Conjecture. Electr. J. Comb., 21(4):P4.29, 2014. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p29.
  19. Jeff Kahn and Gil Kalai. A counterexample to Borsuk’s conjecture. Bull. Amer. Math. Soc., 29:60-62, 1993. URL: https://doi.org/10.1090/S0273-0979-1993-00398-7.
  20. Roman Karasev, Alfredo Hubard, and Boris Aronov. Convex equipartitions: the spicy chicken theorem. Geometriae Dedicata, 170(1):263-279, 2014. URL: https://doi.org/10.1007/s10711-013-9879-5.
  21. J. Mark Keil. Polygon decomposition. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 491-518. North Holland/Elsevier, 2000. URL: https://doi.org/10.1016/b978-044482537-7/50012-7.
  22. Irina Kostitsyna. Balanced partitioning of polygonal domains. PhD thesis, Stony Brook University, Stony Brook, NY, 2015. Google Scholar
  23. Stefan Langerman and Pat Morin. Covering things with things. Discrete & Computational Geometry, 33(4):717-729, 2005. URL: https://doi.org/10.1007/s00454-004-1108-4.
  24. Anil Maheshwari, Jörg-Rüdiger Sack, and Hristo N. Djidjev. Link distance problems. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, chapter 12, pages 519-558. North-Holland, 2000. URL: https://doi.org/10.1016/b978-044482537-7/50013-9.
  25. Nimrod Megiddo and Arie Tamir. On the complexity of locating linear facilities in the plane. Operations Research Letters, 1(5):194-197, 1982. URL: https://doi.org/10.1016/0167-6377(82)90039-6.
  26. Joseph S.B. Mitchell, Valentin Polishchuk, and Mikko Sysikaski. Minimum-link paths revisited. Computational Geometry, 47(6):651-667, 2014. URL: https://doi.org/10.1016/j.comgeo.2013.12.005.
  27. R. Nandakumar and N. Ramana Rao. Fair partitions of polygons: An elementary introduction. Proceedings-Mathematical Sciences, 122(3):459-467, 2012. URL: https://doi.org/10.1007/s12044-012-0076-5.
  28. Jack Robertson and William Webb. Cake-cutting algorithms: Be fair if you can. AK Peters/CRC Press, 1998. Google Scholar
  29. Pablo Soberón. Balanced convex partitions of measures in ℝ^d. Mathematika, 58(1):71-76, 2012. URL: https://doi.org/10.1112/S0025579311001914.
  30. Subhash Suri. On some link distance problems in a simple polygon. IEEE Trans. Robotics and Automation, 6(1):108-113, 1990. URL: https://doi.org/10.1109/70.88124.
  31. Samuel Zahnd, Patrick Lichisteiner, and Tobi Delbruck. Integrated vision sensor for detecting boundary crossings. In 2003 IEEE International Symposium on Circuits and Systems (ISCAS), volume 2, 2003. URL: https://doi.org/10.1109/ISCAS.2003.1205986.
  32. Yunhui Zheng, David J. Brady, and Pankaj K. Agarwal. Localization using boundary sensors: An analysis based on graph theory. ACM Trans. Sen. Netw., 3(4), 2007. URL: https://doi.org/10.1145/1281492.1281496.
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