{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,11]],"date-time":"2025-05-11T04:01:02Z","timestamp":1746936062089,"version":"3.40.5"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:00:00Z","timestamp":1742947200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:00:00Z","timestamp":1742947200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014440","name":"Ministerio de Ciencia, Innovaci\u00f3n y Universidades","doi-asserted-by":"publisher","award":["PID2019-104129GB-I00\/AEI"],"award-info":[{"award-number":["PID2019-104129GB-I00\/AEI"]}],"id":[{"id":"10.13039\/100014440","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["DICYT 042332PL"],"award-info":[{"award-number":["DICYT 042332PL"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100014374","name":"Universitat Polit\u00e8cnica de Catalunya","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100014374","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We explore an extension to rectilinear convexity of the classic problem of computing the convex hull of a set of geometric objects. Namely, we solve the problem of computing the rectilinear convex hull with arbitrary orientation for a set of segments and circles. We describe efficient algorithms to compute and maintain the objects appearing on the boundary of the rectilinear convex hull of such sets, while we rotate the coordinate axes by an angle that goes from 0 to <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$2\\pi $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>\u03c0<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. We first consider a set of <jats:italic>n<\/jats:italic> segments. If the segments are not necessarily disjoint, we describe an algorithm that runs in optimal <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (n\\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> time and <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(n\\alpha (n))$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mi>\u03b1<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> space, where <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\alpha (n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b1<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is the extremely slowly growing inverse of Ackermann\u2019s function. If instead the segments form a simple polygonal chain, we describe an algorithm that improves the previous space complexity to <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. We then extend the techniques used in these algorithms to a set of <jats:italic>n<\/jats:italic> circles. The resulting algorithm runs in optimal <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (n\\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> time and <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> space.<\/jats:p>","DOI":"10.1007\/s10898-025-01482-9","type":"journal-article","created":{"date-parts":[[2025,3,29]],"date-time":"2025-03-29T07:17:28Z","timestamp":1743232648000},"page":"227-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles"],"prefix":"10.1007","volume":"92","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5512-5298","authenticated-orcid":false,"given":"Carlos","family":"Alegr\u00eda","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5539-9037","authenticated-orcid":false,"given":"Justin","family":"Dallant","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8703-8970","authenticated-orcid":false,"given":"Pablo","family":"P\u00e9rez-Lantero","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0095-1725","authenticated-orcid":false,"given":"Carlos","family":"Seara","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,26]]},"reference":[{"issue":"1","key":"1482_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1998.0988","volume":"31","author":"J Basch","year":"1999","unstructured":"Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. J. Algorithms 31(1), 1\u201328 (1999)","journal-title":"J. Algorithms"},{"key":"1482_CR2","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.-D., Delage, C.: Convex hull and Voronoi diagram of additively weighted points. In Algorithms \u2013 ESA 2005, pages 367\u2013378","DOI":"10.1007\/11561071_34"},{"key":"1482_CR3","doi-asserted-by":"crossref","unstructured":"Brodal, G., Jacob, R.: Dynamic planar convex hull. In 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002., pages 617\u2013626","DOI":"10.1109\/SFCS.2002.1181985"},{"key":"1482_CR4","doi-asserted-by":"crossref","unstructured":"Davari, M.\u00a0J., Edalat, A., Lieutier, A.: The convex hull of finitely generable subsets and its predicate transformer. In 2019 34th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). IEEE, jun (2019)","DOI":"10.1109\/LICS.2019.8785680"},{"issue":"8","key":"1482_CR5","doi-asserted-by":"publisher","first-page":"1144","DOI":"10.1093\/comjnl\/bxv124","volume":"59","author":"P P\u00e9rez-Lantero","year":"2016","unstructured":"P\u00e9rez-Lantero, P.: Area and perimeter of the convex hull of stochastic points. Comput. J. 59(8), 1144\u20131154 (2016)","journal-title":"Comput. J."},{"issue":"1","key":"1482_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3046673","volume":"64","author":"P Afshani","year":"2017","unstructured":"Afshani, P., Barbay, J., Chan, T.M.: Instance-optimal geometric algorithms. J. ACM 64(1), 1\u201338 (2017)","journal-title":"J. ACM"},{"issue":"4","key":"1482_CR7","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF02712873","volume":"16","author":"TM Chan","year":"1996","unstructured":"Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geometry 16(4), 361\u2013368 (1996)","journal-title":"Discrete Comput. Geometry"},{"issue":"12","key":"1482_CR8","doi-asserted-by":"publisher","first-page":"1605","DOI":"10.1109\/12.9737","volume":"37","author":"R Miller","year":"1988","unstructured":"Miller, R., Stout, Q.: Efficient parallel convex hull algorithms. IEEE Trans. Comput. 37(12), 1605\u20131618 (1988)","journal-title":"IEEE Trans. Comput."},{"issue":"11","key":"1482_CR9","doi-asserted-by":"publisher","first-page":"115102","DOI":"10.1088\/1572-9494\/ac1da0","volume":"73","author":"C Wang","year":"2021","unstructured":"Wang, C., Zhou, R.-G.: A quantum search algorithm of two-dimensional convex hull. Commun. Theo. Phys. 73(11), 115102 (2021)","journal-title":"Commun. Theo. Phys."},{"key":"1482_CR10","doi-asserted-by":"crossref","unstructured":"Acar, U.\u00a0A., Blelloch, G.\u00a0E., Tangwongsan, K., T\u00fcrko\u011flu, D.: Robust kinetic convex hulls in 3d. In Algorithms - ESA 2008, pages 29\u201340. Springer Berlin Heidelberg, (2008)","DOI":"10.1007\/978-3-540-87744-8_3"},{"issue":"4","key":"1482_CR11","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF02573985","volume":"10","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geometry 10(4), 377\u2013409 (1993)","journal-title":"Discrete Comput. Geometry"},{"issue":"3","key":"1482_CR12","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/s11284-007-0421-9","volume":"23","author":"EB Nilsen","year":"2008","unstructured":"Nilsen, E.B., Pedersen, S., Linnell, J.D.C.: Can minimum convex polygon home ranges be used to draw biologically meaningful conclusions? Ecol. Res. 23(3), 635\u2013639 (2008)","journal-title":"Ecol. Res."},{"issue":"6","key":"1482_CR13","doi-asserted-by":"publisher","first-page":"1621","DOI":"10.1088\/0266-5611\/18\/6\/313","volume":"18","author":"OM Bucci","year":"2002","unstructured":"Bucci, O.M., Capozzoli, A., D\u2019Elia, G.: Determination of the convex hull of radiating or scattering systems: a new, simple and effective approach. Inverse Prob. 18(6), 1621 (2002)","journal-title":"Inverse Prob."},{"issue":"4","key":"1482_CR14","doi-asserted-by":"publisher","first-page":"045303","DOI":"10.1088\/1751-8121\/aa9100","volume":"51","author":"B Regula","year":"2017","unstructured":"Regula, B.: Convex geometry of quantum resource quantification. J. Phys. A: Math. Theor. 51(4), 045303 (2017)","journal-title":"J. Phys. A: Math. Theor."},{"key":"1482_CR15","doi-asserted-by":"crossref","unstructured":"G.\u00a0J. Rawlins and D.\u00a0Wood. Ortho-convexity and its generalizations. In G.\u00a0T. Toussaint, editor, Computational Morphology, volume\u00a06 of Machine Intelligence and Pattern Recognition, pages 137\u2013152. North-Holland, 1988","DOI":"10.1016\/B978-0-444-70467-2.50015-1"},{"issue":"4","key":"1482_CR16","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/BF01933620","volume":"23","author":"TM Nicholl","year":"1983","unstructured":"Nicholl, T.M., Lee, D.-T., Liao, Y.-Z., Wong, C.-K.: On the X-Y convex hull of a set of X-Y polygons. BIT Numer. Math. 23(4), 456\u2013471 (1983)","journal-title":"BIT Numer. Math."},{"issue":"3","key":"1482_CR17","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0255(84)90025-2","volume":"33","author":"T Ottmann","year":"1984","unstructured":"Ottmann, T., Soisalon-Soininen, E., Wood, D.: On the definition and computation of rectilinear convex hulls. Inf. Sci. 33(3), 157\u2013171 (1984)","journal-title":"Inf. Sci."},{"key":"1482_CR18","doi-asserted-by":"crossref","unstructured":"Preparata, F.\u00a0P., Shamos, M.\u00a0I.: Computational geometry: An introduction. Text and monographs in computer science. Springer-Verlag, (1985)","DOI":"10.1007\/978-1-4612-1098-6"},{"issue":"1","key":"1482_CR19","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0020-0190(87)90086-X","volume":"25","author":"AA Melkman","year":"1987","unstructured":"Melkman, A.A.: On-line construction of the convex hull of a simple polyline. Inf. Process. Lett. 25(1), 11\u201312 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1482_CR20","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0925-7721(92)90015-K","volume":"1","author":"D Rappaport","year":"1992","unstructured":"Rappaport, D.: A convex hull algorithm for discs, and applications. Comput. Geom. 1(3), 171\u2013187 (1992)","journal-title":"Comput. Geom."},{"issue":"10","key":"1482_CR21","doi-asserted-by":"publisher","first-page":"1737","DOI":"10.1109\/JRPROC.1959.287109","volume":"47","author":"SH Unger","year":"1959","unstructured":"Unger, S.H.: Pattern detection and recognition. Proceedings of IRE 47(10), 1737\u20131752 (1959)","journal-title":"Proceedings of IRE"},{"key":"1482_CR22","unstructured":"G.\u00a0J.\u00a0E. Rawlins. Explorations in restricted-orientation geometry. PhD thesis, School of Computer Science, University of Waterloo, 1987"},{"issue":"1","key":"1482_CR23","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1137\/19M1303010","volume":"50","author":"H Gonz\u00e1lez-Aguilar","year":"2021","unstructured":"Gonz\u00e1lez-Aguilar, H., Orden, D., P\u00e9rez-Lantero, P., Rappaport, D., Seara, C., Tejel, J., Urrutia, J.: Maximum rectilinear convex subsets. SIAM J. Comput. 50(1), 145\u2013170 (2021)","journal-title":"SIAM J. Comput."},{"key":"1482_CR24","doi-asserted-by":"crossref","unstructured":"Karmakar, N., Biswas, A.: Construction of 3D orthogonal convex hull of a digital object. In Combinatorial Image Analysis, pages 125\u2013142. Springer International Publishing, (2015)","DOI":"10.1007\/978-3-319-26145-4_10"},{"key":"1482_CR25","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.tcs.2020.09.043","volume":"847","author":"MA Aman","year":"2020","unstructured":"Aman, M.A., Sarkar, A., Dutt, M., Biswas, A.: A linear time combinatorial algorithm to compute the relative orthogonal convex hull of digital objects. Theoret. Comput. Sci. 847, 103\u2013121 (2020)","journal-title":"Theoret. Comput. Sci."},{"key":"1482_CR26","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/j.ins.2012.05.029","volume":"216","author":"A Biswas","year":"2012","unstructured":"Biswas, A., Bhowmick, P., Sarkar, M., Bhattacharya, B.B.: A linear-time combinatorial algorithm to find the orthogonal hull of an object on the digital plane. Inf. Sci. 216, 176\u2013195 (2012)","journal-title":"Inf. Sci."},{"issue":"1","key":"1482_CR27","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1002\/net.10035","volume":"40","author":"E Uchoa","year":"2002","unstructured":"Uchoa, E., Poggi de Arag\u00e3o, M., Ribeiro, C.C.: Preprocessing Steiner problems from VLSI layout. Networks 40(1), 38\u201350 (2002)","journal-title":"Networks"},{"key":"1482_CR28","doi-asserted-by":"crossref","unstructured":"Fink, E., Wood, D.:Restricted-orientation Convexity. Monographs in Theoretical Computer Science. Springer-Verlag, (2004)","DOI":"10.1007\/978-3-642-18849-7"},{"issue":"3","key":"1482_CR29","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s004540010069","volume":"25","author":"J Matou\u0161ek","year":"2001","unstructured":"Matou\u0161ek, J.: On directional convexity. Discrete Comput. Geometry 25(3), 389\u2013403 (2001)","journal-title":"Discrete Comput. Geometry"},{"issue":"1","key":"1482_CR30","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/PL00009331","volume":"19","author":"J Matou\u0161ek","year":"1998","unstructured":"Matou\u0161ek, J., Plech\u00e1\u010d, P.: On functional separately convex hulls. Discrete Comput. Geometry 19(1), 105\u2013130 (1998)","journal-title":"Discrete Comput. Geometry"},{"issue":"3","key":"1482_CR31","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/BF02320367","volume":"60","author":"NN Metelskii","year":"1996","unstructured":"Metelskii, N.N., Martynchik, V.N.: Partial convexity. Math. Notes 60(3), 300\u2013305 (1996)","journal-title":"Math. Notes"},{"issue":"8","key":"1482_CR32","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1016\/j.comgeo.2011.04.002","volume":"44","author":"T Biedl","year":"2011","unstructured":"Biedl, T., Gen\u00e7, B.: Reconstructing orthogonal polyhedra from putative vertex sets. Comput. Geometry: Theory Appl. 44(8), 409\u2013417 (2011)","journal-title":"Comput. Geometry: Theory Appl."},{"key":"1482_CR33","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.is.2013.10.001","volume":"40","author":"W Son","year":"2014","unstructured":"Son, W., Hwang, S.-W., Ahn, H.-K.: MSSQ: Manhattan spatial skyline queries. Inf. Syst. 40, 67\u201383 (2014)","journal-title":"Inf. Syst."},{"issue":"3","key":"1482_CR34","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.comgeo.2010.07.005","volume":"44","author":"JM D\u00edaz-Ba\u00f1ez","year":"2011","unstructured":"D\u00edaz-Ba\u00f1ez, J.M., L\u00f3pez, M.A., Mora, M., Seara, C., Ventura, I.: Fitting a two-joint orthogonal chain to a point set. Comput. Geom. 44(3), 135\u2013147 (2011)","journal-title":"Comput. Geom."},{"key":"1482_CR35","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.\u00a0G., Seidel, R.: Output-size sensitive algorithms for finding maximal vectors. In Annual Symposium on Computational Geometry (SoCG\u201985), pages 89\u201396. ACM, (1985)","DOI":"10.1145\/323233.323246"},{"issue":"6","key":"1482_CR36","doi-asserted-by":"publisher","first-page":"1858","DOI":"10.1137\/S0097539798348365","volume":"29","author":"S Kapoor","year":"2000","unstructured":"Kapoor, S.: Dynamic maintenance of maxima of 2D point sets. SIAM J. Comput. 29(6), 1858\u20131877 (2000)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1482_CR37","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00453-004-1082-5","volume":"39","author":"AL Buchsbaum","year":"2004","unstructured":"Buchsbaum, A.L., Goodrich, M.T.: Three-dimensional layers of maxima. Algorithmica 39(4), 275\u2013286 (2004)","journal-title":"Algorithmica"},{"issue":"3","key":"1482_CR38","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/s10898-020-00953-5","volume":"70","author":"C Alegr\u00eda-Galicia","year":"2021","unstructured":"Alegr\u00eda-Galicia, C., Orden, D., Seara, C., Urrutia, J.: Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations. J. Global Optim. 70(3), 687\u2013714 (2021)","journal-title":"J. Global Optim."},{"key":"1482_CR39","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1007\/s10898-022-01238-9","volume":"85","author":"C Alegr\u00eda-Galicia","year":"2023","unstructured":"Alegr\u00eda-Galicia, C., Orden, D., Seara, C., Urrutia, J.: Separating bichromatic point sets in the plane by restricted orientation convex hulls. J. Global Optim. 85, 1003\u20131036 (2023)","journal-title":"J. Global Optim."},{"key":"1482_CR40","doi-asserted-by":"crossref","unstructured":"P\u00e9rez-Lantero, P., Seara, C., Urrutia, J.: Rectilinear convex hull of points in 3D. In Proceedings of LATIN 2020, LNCS 12118, (2020)","DOI":"10.1007\/978-3-030-61792-9_24"},{"key":"1482_CR41","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/j.comgeo.2017.06.003","volume":"68","author":"C Alegr\u00eda-Galicia","year":"2018","unstructured":"Alegr\u00eda-Galicia, C., Orden, D., Seara, C., Urrutia, J.: On the $${\\cal{O} }_\\beta $$-hull of a planar point set. Comput. Geometry: Theory Appl. 68, 277\u2013291 (2018)","journal-title":"Comput. Geometry: Theory Appl."},{"issue":"1","key":"1482_CR42","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s00453-022-01002-1","volume":"85","author":"SW Bae","year":"2023","unstructured":"Bae, S.W., Yoon, S.D.: Empty squares in arbitrary orientation among points. Algorithmica 85(1), 29\u201374 (2023)","journal-title":"Algorithmica"},{"issue":"2","key":"1482_CR43","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1111\/cgf.13147","volume":"36","author":"M Livesu","year":"2017","unstructured":"Livesu, M., Ellero, S., Mart\u00ednez, J., Lefebvre, S., Attene, M.: From 3D models to 3D prints: an overview of the processing pipeline. Comput. Graphics Forum 36(2), 537\u2013564 (2017)","journal-title":"Comput. Graphics Forum"},{"issue":"5","key":"1482_CR44","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1111\/cgf.12437","volume":"33","author":"J Vanek","year":"2014","unstructured":"Vanek, J., Galicia, J.A.G., Benes, B.: Clever support: Efficient support structure generation for digital fabrication. Comput. Graphics Forum 33(5), 117\u2013125 (2014)","journal-title":"Comput. Graphics Forum"},{"key":"1482_CR45","unstructured":"S.\u00a0Schuierer and D.\u00a0Wood. Restricted-orientation visibility. Technical Report\u00a040, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, 1991"},{"key":"1482_CR46","unstructured":"Fran\u011bk, V.: On Algorithmic Characterization of Functional$$D$$-convex Hulls. PhD thesis, Faculty of Mathematics and Physics, Charles University in Prague, (2008)"},{"issue":"1","key":"1482_CR47","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.comgeo.2008.03.003","volume":"42","author":"V Fran\u011bk","year":"2009","unstructured":"Fran\u011bk, V., Matou\u0161ek, J.: Computing $$D$$-convex hulls in the plane. Computat. Geometry: Theory Appl. 42(1), 81\u201389 (2009)","journal-title":"Computat. Geometry: Theory Appl."},{"key":"1482_CR48","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J Hershberger","year":"1989","unstructured":"Hershberger, J.: Finding the upper envelope of $$n$$ line segments in $${O}(n\\log n)$$ time. Inf. Process. Lett. 33, 169\u2013174 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1482_CR49","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF02187894","volume":"3","author":"A Wiernik","year":"1988","unstructured":"Wiernik, A., Sharir, M.: Planar realizations of nonlinear Davenport-Schinzel sequences by segments. Discrete Comput. Geometry 3(1), 15\u201347 (1988)","journal-title":"Discrete Comput. Geometry"},{"key":"1482_CR50","unstructured":"M.\u00a0Sharir and P.\u00a0K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, 1995"},{"issue":"3","key":"1482_CR51","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(95)00132-V","volume":"56","author":"O Devillers","year":"1995","unstructured":"Devillers, O., Golin, M.J.: Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas. Inf. Process. Lett. 56(3), 157\u2013164 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1482_CR52","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K Kedem","year":"1986","unstructured":"Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geometry 1(1), 59\u201371 (1986)","journal-title":"Discrete Comput. Geometry"},{"key":"1482_CR53","doi-asserted-by":"crossref","unstructured":"I.\u00a0S\u00e1nchez\u00a0Ramos, F.\u00a0Meseguer-Garrido, J.\u00a0J. Aliaga, and J.\u00a0Grau. Generalization of the pedal concept in bidimensional spaces. Application to lima\u00e7on of Pascal. DYNA, 88:196\u2013202, 2021","DOI":"10.15446\/dyna.v88n216.88507"},{"key":"1482_CR54","unstructured":"Dennis, L.:A catalog of special plane curves. Dover Publication, Inc, (1972)"},{"key":"1482_CR55","unstructured":"contributors, W.:Lima\u00e7on \u2014 Wikipedia, the free encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Lima%C3%A7on&oldid=1212969048, 2024. [Online; accessed 29-September-2024]"},{"key":"1482_CR56","doi-asserted-by":"crossref","unstructured":"Driscoll, J.\u00a0R., Sarnak, N., Sleator, D.\u00a0D., Tarjan, R.\u00a0E.: Making data structures persistent. In J.\u00a0Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 109\u2013121. ACM, (1986)","DOI":"10.1145\/12130.12142"},{"key":"1482_CR57","doi-asserted-by":"crossref","unstructured":"Alegr\u00eda, C., Dallant, J., P\u00e9rez-Lantero, P., Seara, C.: The rectilinear convex hull of line segments. 24th International Symposium on Fundamentals of Computation Theory, FCT 2023, LNCS, Vol. 14292","DOI":"10.1007\/978-3-031-43587-4_3"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01482-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-025-01482-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01482-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,10]],"date-time":"2025-05-10T03:23:24Z","timestamp":1746847404000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-025-01482-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,26]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["1482"],"URL":"https:\/\/doi.org\/10.1007\/s10898-025-01482-9","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2025,3,26]]},"assertion":[{"value":"24 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}