{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T03:21:57Z","timestamp":1771903317427,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T00:00:00Z","timestamp":1714780800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T00:00:00Z","timestamp":1714780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100023561","name":"Ministerio de Universidades","doi-asserted-by":"publisher","award":["PID2019-104129GB-I00\/ MCIN\/ AEI\/ 10.13039\/501100011033"],"award-info":[{"award-number":["PID2019-104129GB-I00\/ MCIN\/ AEI\/ 10.13039\/501100011033"]}],"id":[{"id":"10.13039\/501100023561","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2024,10]]},"abstract":"Abstract<\/jats:title>Let P<\/jats:italic> be a set of n<\/jats:italic> points in $$\\mathbb {R}^3$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in general position, and let RCH<\/jats:italic>(P<\/jats:italic>) be the rectilinear convex hull of P<\/jats:italic>. In this paper we obtain an optimal $$O(n\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time and O<\/jats:italic>(n<\/jats:italic>) space algorithm to compute RCH<\/jats:italic>(P<\/jats:italic>). We also obtain an efficient $$O(n\\log ^2 n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time and $$O(n\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of P<\/jats:italic> as we rotate $${\\mathbb {R}}^3$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> around the Z<\/jats:italic>-axis. We study some combinatorial properties of the rectilinear convex hulls of point sets in $$\\mathbb {R}^3$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Finally, as an application of the obtained results, we show an approximation algorithm to an optimization fitting problem in $$\\mathbb {R}^3$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s10898-024-01402-3","type":"journal-article","created":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T02:01:21Z","timestamp":1714788081000},"page":"551-571","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Rectilinear convex hull of points in 3D and applications"],"prefix":"10.1007","volume":"90","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8703-8970","authenticated-orcid":false,"given":"Pablo","family":"P\u00e9rez-Lantero","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0095-1725","authenticated-orcid":false,"given":"Carlos","family":"Seara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4158-5979","authenticated-orcid":false,"given":"Jorge","family":"Urrutia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,4]]},"reference":[{"key":"1402_CR1","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} $$-hull of planar point sets. Comput. Geom.: Theory Appl. 68, 277\u2013291 (2018)","journal-title":"Comput. Geom.: Theory Appl."},{"issue":"3","key":"1402_CR2","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/s10898-020-00953-5","volume":"79","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. 79(3), 687\u2013714 (2021). https:\/\/doi.org\/10.1007\/s10898-020-00953-5","journal-title":"J. Global Optim."},{"key":"1402_CR3","unstructured":"Alegr\u00eda-Galicia, C., Orden, D., Seara, C., Urrutia. J.: Optimizing an oriented convex hull with two directions. In: European Workshop on Computational Geometry (2015)"},{"key":"1402_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-022-01238-9","author":"C Alegr\u00eda-Galicia","year":"2022","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. (2022). https:\/\/doi.org\/10.1007\/s10898-022-01238-9","journal-title":"J. Global Optim."},{"issue":"7","key":"1402_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112424","volume":"344","author":"G Ambrus","year":"2021","unstructured":"Ambrus, G., Nielsen, P., Wilson, C.: New estimates for convex layer numbers. Discrete Math. 344(7), 112424 (2021)","journal-title":"Discrete Math."},{"issue":"1","key":"1402_CR6","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1137\/S0097539794277871","volume":"28","author":"D Avis","year":"1999","unstructured":"Avis, D., Beresford-Smith, B., Devroye, L., Elgindy, H., Gu\u00e9vremont, E., Hurtado, F., Zhu, B.: Unoriented $$\\Theta $$-maxima in the plane: complexity and algorithms. SIAM J. Comput. 28(1), 278\u2013296 (1999)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"1402_CR7","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1016\/j.comgeo.2009.02.006","volume":"42","author":"SW Bae","year":"2009","unstructured":"Bae, S.W., Lee, Ch., Ahn, H.-K., Choi, S., Chwa, K.-Y.: Computing minimum-area rectilinear convex hull and L-shape. Comput. Geom.: Theory Appl. 42(9), 903\u2013912 (2009)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"1402_CR8","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.dam.2017.11.005","volume":"280","author":"B Bhattacharya","year":"2020","unstructured":"Bhattacharya, B., Das, S., Kameda, T.: Linear-time fitting of a $$k$$-step function. Discrete Appl. Math. 280, 43\u201352 (2020)","journal-title":"Discrete Appl. Math."},{"issue":"8","key":"1402_CR9","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. Geom.: Theory Appl. 44(8), 409\u2013417 (2011)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"1402_CR10","doi-asserted-by":"crossref","unstructured":"Biswas, A., Bhowmick, P., Sarkar, M., Bhattacharya B.B.: Finding the orthogonal hull of a digital object: a combinatorial approach. In: Proceedings of the 12th International Conference on Combinatorial Image Analysis, IWCIA\u201908, pp. 124\u2013135 (2008)","DOI":"10.1007\/978-3-540-78275-9_11"},{"key":"1402_CR11","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 617\u2013626 (2002)","DOI":"10.1109\/SFCS.2002.1181985"},{"issue":"4","key":"1402_CR12","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"},{"key":"1402_CR13","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/TIT.1985.1057060","volume":"31","author":"B Chazelle","year":"1985","unstructured":"Chazelle, B.: On the convex layers of a planar set. IEEE Trans. Inf. Theory 31, 509\u2013517 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1402_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2020.112029","volume":"343","author":"I Choi","year":"2020","unstructured":"Choi, I., Joo, W., Kim, M.: The layer number of $$\\alpha $$-evenly distributed point sets. Discrete Math. 343, 112029 (2020)","journal-title":"Discrete Math."},{"issue":"3","key":"1402_CR15","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.: Theory Appl. 44(3), 135\u2013147 (2011)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"1402_CR16","doi-asserted-by":"crossref","unstructured":"Fink, E., Wood, D.: Restricted-Orientation Convexity. Monographs in Theoretical Computer Science (An EATCS Series). Springer (2004)","DOI":"10.1007\/978-3-642-18849-7"},{"issue":"1","key":"1402_CR17","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. Comput. Geom.: Theory Appl. 42(1), 81\u201389 (2009)","journal-title":"Comput. Geom.: Theory Appl."},{"issue":"1","key":"1402_CR18","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":"1402_CR19","unstructured":"G\u00fcting, R.H.: Conquering contours: efficient algorithms for computational geometry. Ph.D. thesis, Fachbereich Informatik, Universit\u00e4t Dortmund (1983)"},{"key":"1402_CR20","doi-asserted-by":"crossref","unstructured":"He, M., Nguyen, C.P., Zeh, N.: Maximal and convex layers of random point sets. LATIN 2018, Lecture Notes in Computer Science, vol. 10807","DOI":"10.1007\/978-3-319-77404-6_44"},{"issue":"5","key":"1402_CR21","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1109\/34.6790","volume":"10","author":"ME Houle","year":"1988","unstructured":"Houle, M.E., Toussaint, G.T.: Computing the width of a set. IEEE Trans. Pattern Anal. Mach. Intell. 10(5), 761\u2013765 (1988)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"4","key":"1402_CR22","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"H-T Kung","year":"1975","unstructured":"Kung, H.-T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. ACM 22(4), 469\u2013476 (1975)","journal-title":"J. ACM"},{"issue":"3","key":"1402_CR23","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":"1402_CR24","unstructured":"Pel\u00e1ez, C., Ram\u00edrez-Vigueras, A., Seara, C., Urrutia, J.: On the rectilinear convex layers of a planar set. In: Mexican Conference on Discrete Mathematics and Computational Geometry, 60th Birthday of Jorge Urrutia (2013)"},{"key":"1402_CR25","doi-asserted-by":"publisher","unstructured":"P\u00e9rez-Lantero, P., Seara, C., Urrutia, J.: Rectilinear convex hull of points in 3D. In: 14th Latin American Theoretical Informatics Symposium, S\u00e3o Paulo, Brazil, January 5\u20138, (2021), LNCS 12118, pp. 296\u2013307. https:\/\/doi.org\/10.1007\/978-3-030-61792-9-24","DOI":"10.1007\/978-3-030-61792-9-24"},{"key":"1402_CR26","doi-asserted-by":"crossref","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An introduction. Springer (1985)","DOI":"10.1007\/978-1-4612-1098-6"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01402-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-024-01402-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01402-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T05:02:23Z","timestamp":1726894943000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-024-01402-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,4]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1402"],"URL":"https:\/\/doi.org\/10.1007\/s10898-024-01402-3","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,4]]},"assertion":[{"value":"28 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}