{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:51:37Z","timestamp":1760151097838,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T00:00:00Z","timestamp":1644537600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002527","name":"Kyonggi University","doi-asserted-by":"publisher","award":["Research Grant 2021"],"award-info":[{"award-number":["Research Grant 2021"]}],"id":[{"id":"10.13039\/501100002527","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The minimum-area parallelogram annulus problem is studied, in which one wants to compute a parallelogram annulus of minimum area that includes n input points in the plane. Extending an usual, doughnut-shaped circular annulus, a parallelogram annulus is defined to be a region between two edge-parallel parallelograms. As a parallelogram has two distinct orientations for its sides, so does a parallelogram annulus as well. In this paper, several variants of the problem are considered: (1) when both side orientations are given and fixed, (2) when one of them is fixed and the other can be freely chosen, (3) when the interior angles of the resulting parallelogram annulus is given and fixed, and (4) when both side orientations can be chosen arbitrarily. The first and efficient algorithms for each of these cases are presented, whose running times are (1) O(n), (2) O(n2logn), (3) O(n2logn), and (4) O(n4+\u03f5), respectively. Further, bicriteria variants of the problem are considered, in which both width and area of the resulting parallelogram annulus are simultaneously minimized. In order to obtain these new algorithms, geometric observations, newly obtained in this paper and known in previous papers, and the symmetric nature of parallelograms and parallelogram annuli are exploited.<\/jats:p>","DOI":"10.3390\/sym14020359","type":"journal-article","created":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T05:14:43Z","timestamp":1644556483000},"page":"359","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Minimum-Area Parallelogram Annulus Problem"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8802-4247","authenticated-orcid":false,"given":"Sang Won","family":"Bae","sequence":"first","affiliation":[{"name":"Division of AI Computer Science and Engineering, Kyonggi University, 16227 Suwon, Korea"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1137\/0212052","article-title":"Linear-Time Algorithms for Linear Programming in R3 and Related Problems","volume":"12","author":"Megiddo","year":"1983","journal-title":"SIAM J. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., and Suri, S. (1987, January 8\u201311). Fast algorithm for computing the largest empty rectangle. Proceedings of the Third Annual Symposium on Computational Geometry (SoCG 1987), Kyoto, Japan.","DOI":"10.1145\/41958.41988"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01840377","article-title":"A new algorithm for largest empty rectangle problem","volume":"5","author":"Orlowski","year":"1990","journal-title":"Algorithmica"},{"key":"ref_4","unstructured":"Ebara, H., Fukuyama, N., Nakano, H., and Nakanishi, Y. Roundness algorithms using the Voronoi diagrams. Proceedings of the Abstracts 1st Canadian Conference Computational Geometry (CCCG), Montreal, QC, Canada."},{"key":"ref_5","unstructured":"Wainstein, A. A non-monotonous placement problem in the plane. Proceedings of the Software Systems for Solving Optimal Planning Problems, Abstract 9th All-Union Symp. USSR, Symp."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0010-4485(92)90035-9","article-title":"Establishment of a pair of concentric circles with the minimum radial separation for assessing roundness error","volume":"24","author":"Roy","year":"1992","journal-title":"Comput.-Aided Des."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1006\/jagm.1994.1038","article-title":"Applications of parametric searching in geometric optimization","volume":"17","author":"Agarwal","year":"1994","journal-title":"J. Algo."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/BF02712871","article-title":"Efficient randomized algorithms for some geometric optimization problems","volume":"16","author":"Agarwal","year":"1996","journal-title":"Discret. Comput. Geom."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1145\/1008731.1008736","article-title":"Approximating extent measures of points","volume":"51","author":"Agarwal","year":"2004","journal-title":"J. ACM"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1142\/S0218195902000748","article-title":"Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus","volume":"12","author":"Chan","year":"2002","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"ref_11","unstructured":"Abellanas, M., Hurtado, F., Icking, C., Ma, L., Palop, B., and Ramos, P. (2003, January 24\u201326). Best Fitting Rectangles. Proceedings of the Euro. Workshop Comput. Geom. (EuroCG 2003), Bonn, Germany."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/j.orl.2009.02.007","article-title":"An optimal O(nlogn) algorithm for finding an enclosing planar rectilinear annulus of minimum width","volume":"37","author":"Gluchshenko","year":"2009","journal-title":"Oper. Res. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.tcs.2012.02.041","article-title":"Minimum-width rectangular annulus","volume":"508","author":"Mukherjee","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2016.11.010","article-title":"Computing a Minimum-Width Square Annulus in Arbitrary Orientation","volume":"718","author":"Bae","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"101697","DOI":"10.1016\/j.comgeo.2020.101697","article-title":"On the minimum-area rectangular and square annulus problem","volume":"92","author":"Bae","year":"2021","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_16","unstructured":"Bae, S.W., and Yoon, S.D. (2020, January 22\u201326). Empty Squares in Arbitrary Orientation Among Points. Proceedings of the 36th Symposium on Computational Geometry (SoCG 2020), Z\u00fcrich, Switzerland. LIPIcs."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.tcs.2020.05.045","article-title":"Minimum-width double-strip and parallelogram annulus","volume":"833","author":"Bae","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"78","DOI":"10.5626\/JCSE.2021.15.2.78","article-title":"Minimum-Width Parallelogram Annulus with Given Angles","volume":"15","author":"Bae","year":"2021","journal-title":"J. Comput. Sci. Eng."},{"key":"ref_19","unstructured":"Lyons, R.G. (2022, January 18). Sum of Two Sinusoids. Available online: https:\/\/dspguru.com\/files\/Sum_of_Two_Sinusoids.pdf."},{"key":"ref_20","unstructured":"Toussaint, G. (1983, January 24\u201326). Solving geometric problems with the rotating calipers. Proceedings of the IEEE MELECON, Athens, Greece."},{"key":"ref_21","unstructured":"Sharir, M., and Agarwal, P.K. (1995). Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","article-title":"Finding the upper envelope of n line segments in O(nlogn) time","volume":"33","author":"Hershberger","year":"1989","journal-title":"Inform. Proc. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. (2000). Computationsl Geometry: Alogorithms and Applications, Springer. [2nd ed.].","DOI":"10.1007\/978-3-662-04245-8"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0925-7721(95)00007-0","article-title":"On-line construction of the upper envelope of triangles and surface patches in three dimensions","volume":"5","author":"Boissonnat","year":"1996","journal-title":"Comput. Geom.: Theory Appl."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/2\/359\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:18:10Z","timestamp":1760134690000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/2\/359"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,11]]},"references-count":24,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["sym14020359"],"URL":"https:\/\/doi.org\/10.3390\/sym14020359","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2022,2,11]]}}}