LIPIcs.ISAAC.2019.25.pdf
- Filesize: 0.56 MB
- 14 pages
Document
Minimum-Width Double-Strip and Parallelogram Annulus
Author
Sang Won Bae 
-
Part of:
Volume:
30th International Symposium on Algorithms and Computation (ISAAC 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-11-28
File
Document Identifiers
Author Details
Cite AsGet BibTex
Sang Won Bae. Minimum-Width Double-Strip and Parallelogram Annulus. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.25
https://doi.org/10.4230/LIPIcs.ISAAC.2019.25
Abstract
In this paper, we study the problem of computing a minimum-width double-strip or parallelogram annulus that encloses a given set of n points in the plane. A double-strip is a closed region in the plane whose boundary consists of four parallel lines and a parallelogram annulus is a closed region between two edge-parallel parallelograms. We present several first algorithms for these problems. Among them are O(n^2) and O(n^3 log n)-time algorithms that compute a minimum-width double-strip and parallelogram annulus, respectively, when their orientations can be freely chosen.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- geometric covering
- parallelogram annulus
- two-line center
- double-strip
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
M. Abellanas, Ferran Hurtado, C. Icking, L. Ma, B. Palop, and P.A. Ramos. Best Fitting Rectangles. In Proc. Euro. Workshop Comput. Geom. (EuroCG 2003), 2003.
-
P. Agarwal and M. Sharir. Planar geometric location problems. Algorithimca, 11:185-195, 1994.
-
P.K. Agarwal and M. Sharir. Efficient randomized algorithms for some geometric optimization problems. Discrete Comput. Geom., 16:317-337, 1996.
-
P.K. Agarwal, M. Sharir, and S. Toledo. Applications of parametric searching in geometric optimization. J. Algo., 17:292-318, 1994.
-
Sang Won Bae. Computing a Minimum-Width Square Annulus in Arbitrary Orientation. Theoret. Comput. Sci., 718:2-13, 2018.
- Sang Won Bae. On the Minimum-Area Rectangular and Square Annulus Problem. CoRR, 2019. URL: http://arxiv.org/abs/1904.06832.
-
Mark de Berg, Mark van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computationsl Geometry: Alogorithms and Applications. Springer-Verlag, 2nd edition, 2000.
-
Alex Glozman, Klara Kedem, and Gregory Shpitalnik. On some geometric selection and optimization problems via sorted matrices. Comput. Geom.: Theory Appl., 11(1):17-28, 1998.
-
Olga N. Gluchshenko, Horst W. Hamacher, and Arie Tamir. An optimal O(n log n) algorithm for finding an enclosing planar rectilinear annulus of minimum width. Operations Research Lett., 37(3):168-170, 2009.
-
J. Hershberger. Finding the upper envelope of n line segments in O(nlog n) time. Inform. Proc. Lett., 33:169-174, 1989.
-
Jerzy Jaromczyk and Miroslaw Kowaluk. The Two-Line Center Problem from a Polar View: A New Algorithm and Data Structure. In Proc. 4th Int. Workshop Algo. Data Struct. (WADS 1995), volume 955 of Lecture Notes Comput. Sci., pages 13-25, 1995.
-
J. Mukherjee, P.R.S. Mahapatra, A. Karmakar, and S. Das. Minimum-width rectangular annulus. Theoretical Comput. Sci., 508:74-80, 2013.
-
U. Roy and X. Zhang. Establishment of a pair of concentric circles with the minimum radial separation for assessing roundness error. Computer-Aided Design, 24(3):161-168, 1992.
-
G.T. Toussaint. Solving geometric problems with the rotating calipers. In Proc. IEEE MELECON, 1983.