Document Open Access Logo

Inscribing or Circumscribing a Histogon to a Convex Polygon

Authors Jaehoon Chung, Sang Won Bae , Chan-Su Shin , Sang Duk Yoon , Hee-Kap Ahn

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.13.pdf
  • Filesize: 0.85 MB
  • 16 pages

Document Identifiers

Author Details

Jaehoon Chung
  • Department of Computer Science and Engineering, Pohang University of Science and Technology, Korea
Sang Won Bae
  • Division of Computer Science and Engineering, Kyonggi University, Suwon, Korea
Chan-Su Shin
  • Division of Computer Engineering, Hankuk University of Foreign Studies, Seoul, Korea
Sang Duk Yoon
  • Department of Service and Design Engineering, SungShin Women’s University, Seoul, Korea
Hee-Kap Ahn
  • Graduate School of Artificial Intelligence, Department of Computer Science and Engineering, Pohang University of Science and Technology, Korea

Funding

This research was partly supported by the Institute of Information & communications Technology Planning & Evaluation(IITP) grant funded by the Korea government(MSIT) (No. 2017-0-00905, Software Star Lab (Optimal Data Structure and Algorithmic Applications in Dynamic Geometric Environment)) and (No. 2019-0-01906, Artificial Intelligence Graduate School Program(POSTECH)).
  • Bae, Sang Won: supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2018R1D1A1B07042755).
  • Shin, Chan-Su: supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT) (No. 2019R1F1A1058963).
  • Yoon, Sang Duk: supported by "Cooperative Research Program for Agriculture Science & Technology Development (Project No. PJ015269032022)" Rural Development Administration, Republic of Korea.

Cite AsGet BibTex

Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn. Inscribing or Circumscribing a Histogon to a Convex Polygon. 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. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.13

Abstract

We consider two optimization problems of approximating a convex polygon, one by a largest inscribed histogon and the other by a smallest circumscribed histogon. An axis-aligned histogon is an axis-aligned rectilinear polygon such that every horizontal edge has an integer length. A histogon of orientation θ is a copy of an axis-aligned histogon rotated by θ in counterclockwise direction. The goal is to find a largest inscribed histogon and a smallest circumscribed histogon over all orientations in [0,π). Depending on whether the horizontal width of a histogon is predetermined or not, we consider several different versions of the problem and present exact algorithms. These optimization problems belong to shape analysis, classification, and simplification, and they have applications in various cost-optimization problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Shape simplification
  • Shape analysis
  • Histogon
  • Convex polygon

Metrics

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

References

  1. Alok Aggarwal, Maria M Klawe, Shlomo Moran, Peter Shor, and Robert Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2(1):195-208, 1987. Google Scholar
  2. Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, and Joachim Gudmundsson. Aperture-angle and hausdorff-approximation of convex figures. Discrete & Computational Geometry, 40(3):414-429, 2008. Google Scholar
  3. Hee-Kap Ahn, Peter Brass, Otfried Cheong, Hyeon-Suk Na, Chan-Su Shin, and Antoine Vigneron. Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets. Computational Geometry, 33(3):152-164, 2006. Google Scholar
  4. Gill Barequet and Vadim Rogol. Maximizing the area of an axially symmetric polygon inscribed in a simple polygon. Computers & Graphics, 31(1):127-136, 2007. Google Scholar
  5. Binay Bhattacharya and Asish Mukhopadhyay. On the minimum perimeter triangle enclosing a convex polygon. In Proc. Japanese Conference on Discrete and Computational Geometry (JCDCG 2002), pages 84-96, 2002. Google Scholar
  6. Sergio Cabello, Otfried Cheong, Christian Knauer, and Lena Schlipf. Finding largest rectangles in convex polygons. Computational Geometry, 51:67-74, 2016. Google Scholar
  7. Tauã M. Cabreira, Lisane B. Brisolara, and Paulo R. Ferreira Jr. Survey on coverage path planning with unmanned aerial vehicles. Drones, 3(1), 2019. Google Scholar
  8. Jyun-Sheng Chang and Chee-Keng Yap. A polynomial solution for the potato-peeling problem. Discrete & Computational Geometry, 1(2):155-182, 1986. Google Scholar
  9. Siu-Wing Cheng, Otfried Cheong, Hazel Everett, and Rene Van Oostrum. Hierarchical decompositions and circular ray shooting in simple polygons. Discrete & Computational Geometry, 32(3):401-415, 2004. Google Scholar
  10. Yujin Choi, Seungjun Lee, and Hee-Kap Ahn. Maximum-area and maximum-perimeter rectangles in polygons. Computational Geometry, 94:101710, 2021. Google Scholar
  11. Howie Choset. Coverage for robotics - A survey of recent results. Annals of Mathematics and Artificial Intelligence, 31:113-126, October 2001. Google Scholar
  12. Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duck Yoon, and Hee-Kap Ahn. Approximating convex polygons by histogons. In Proc. 34th Canadian Conference on Computational Geometry (CCCG 2022), 2022. Google Scholar
  13. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications, chapter Point Location, pages 121-146. Springer-Verlag TELOS, 3rd edition, 2008. Google Scholar
  14. A DePano, Yan Ke, and Joseph O’Rourke. Finding largest inscribed equilateral triangles and squares. In Proc. 25th Allerton Conference on Communications, Control and Computing, pages 869-878, 1987. Google Scholar
  15. Enric Galceran and Marc Carreras. A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 61(12):1258-1276, 2013. Google Scholar
  16. Martin Held. On the Computational Geometry of Pocket Machining. Lecture Notes in Computer Science. Springer Verlag, 1991. Google Scholar
  17. Kai Jin and Kevin Matulef. Finding the maximum area parallelogram in a convex polygon. In Proc. 23rd Canadian Conference on Computational Geometry (CCCG 2011), 2011. Google Scholar
  18. Christian Knauer, Lena Schlipf, Jens M Schmidt, and Hans Raj Tiwary. Largest inscribed rectangles in convex polygons. Journal of discrete algorithms, 13:78-85, 2012. Google Scholar
  19. Seungjun Lee, Taekang Eom, and Hee-Kap Ahn. Largest triangles in a polygon. Computational Geometry, 98:101792, 2021. Google Scholar
  20. Elefterios A. Melissaratos and Diane L. Souvaine. On solving geometric optimization problems using shortest paths. In Proc. 6th Annual Symposium on Computational Geometry (SCG '90), pages 350-359, 1990. Google Scholar
  21. Joseph O'Rourke, Alok Aggarwal, Sanjeev Maddila, and Michael Baldwin. An optimal algorithm for finding minimal enclosing triangles. Journal of Algorithms, 7(2):258-269, 1986. Google Scholar
  22. Christian Schwarz, Jürgen Teich, Alek Vainshtein, Emo Welzl, and Brian L. Evans. Minimal enclosing parallelogram with application. In Proc. 11th Annual Symposium on Computational Geometry (SCG '95), pages 434-435, 1995. Google Scholar
  23. Godfried Toussaint. Solving geometric problems with the rotating calipers. In Proc. Mediterranean Electrotechnical Conference (MELECON'83), 1983. Google Scholar
  24. Ivor van der Hoog, Vahideh Keikha, Maarten Löffler, Ali Mohades, and Jérôme Urhausen. Maximum-area triangle in a convex polygon, revisited. Information Processing Letters, 161:105943, 2020. 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 Imprint Privacy Contact