{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:53Z","timestamp":1787340833877,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Finding the coordinatewise maxima and the convex hull of a planar point set are probably the most classic problems in computational geometry. We consider these problems in the self-improving setting. Here, we have $n$ distributions $\\mathcal{D}_1, \\ldots, \\mathcal{D}_n$ of planar points. An input point set $(p_1, \\ldots, p_n)$ is generated by taking an independent sample $p_i$ from each $\\mathcal{D}_i$, so the input is distributed according to the product $\\mathcal{D} = \\prod_i \\mathcal{D}_i$. A self-improving algorithm repeatedly gets inputs from the distribution $\\mathcal{D}$ (which is a priori unknown), and it tries to optimize its running time for $\\mathcal{D}$. The algorithm uses the first few inputs to learn salient features of the distribution $\\mathcal{D}$ before it becomes fine-tuned to $\\mathcal{D}$. Let $\\text{OPT-MAX}_\\mathcal{D}$ (resp., $\\text{OPT-CH}_\\mathcal{D}$) be the expected depth of an optimal linear comparison tree computing the maxima (resp., convex hull) for $\\mathcal{D}$. Our maxima algorithm eventually achieves expected running time $O(\\text{OPT-MAX}_\\mathcal{D} + n)$. Furthermore, we give a self-improving algorithm for convex hulls with expected running time $O(\\text{OPT-CH}_\\mathcal{D} + n\\log\\log n)$. Our results require new tools for understanding linear comparison trees. In particular, we convert a general linear comparison tree to a restricted version that can then be related to the running time of our algorithms. Another interesting feature is an interleaved search procedure to determine the likeliest point to be extremal with minimal computation. This allows our algorithms to be competitive with the optimal algorithm for $\\mathcal{D}$.<\/jats:p>","DOI":"10.1137\/12089702x","type":"journal-article","created":{"date-parts":[[2014,4,17]],"date-time":"2014-04-17T11:41:40Z","timestamp":1397734900000},"page":"617-653","source":"Crossref","is-referenced-by-count":3,"title":["Self-Improving Algorithms for Coordinatewise Maxima and Convex Hulls"],"prefix":"10.1137","volume":"43","author":[{"given":"Kenneth L.","family":"Clarkson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,4,17]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"P. Afshani, J. Barbay, and T. M. Chan,\n                      Instance-optimal geometric algorithms\n                      , in Proceedings of the 50th Annual IEEE Symposium on the Foundations of Computer Science (FOCS), 2009, pp. 129-138.","DOI":"10.1109\/FOCS.2009.34"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/090766437"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"N. Ailon, B. Chazelle, S. Comandur, and D. Liu,\n                      Self-improving algorithms\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium of Discrete Algorithms (SODA), 2006, pp. 261-270.","DOI":"10.1145\/1109557.1109587"},{"key":"atypb4","unstructured":"J. Barbay,\n                      Adaptive (Analysis of) Algorithms for Convex Hulls and Related Problems\n                      , available online from http:\/\/swp.dcc.uchile.cl\/TR\/2008\/TR_DCC-2008-017.pdf, 2008."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars,\n                      Computational Geometry: Algorithms and Applications\n                      , 3rd ed., Springer-Verlag, Berlin, 2008.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"atypb6","unstructured":"P. Bose, L. Devroye, K. Dou\u00efeb, V. Dujmovi\u0107, J. King, and P. Morin,\n                      Odds-On Trees\n                      , preprint, arXiv:1002.1092, 2010."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9430-0"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90156-7"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189314"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187879"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, W. Mulzer, and C. Seshadhri,\n                      Self-improving algorithms for convex hulls\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium of Discrete Algorithms (SODA), 2010, pp. 1546-1565.","DOI":"10.1137\/1.9781611973075.126"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, W. Mulzer, and C. Seshadhri,\n                      Self-improving algorithms for coordinate-wise maxima\n                      , in Proceedings of the 28th Annual ACM Symposium on Computer Geometry (SoCG), 2012, pp. 277-286.","DOI":"10.1145\/2261250.2261291"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson and C. Seshadhri,\n                      Self-improving algorithms for Delaunay triangulations\n                      , in Proceedings of the 24th Annual ACM Symposium on Computer Geometry (SoCG), 2008, pp. 226-232.","DOI":"10.1145\/1377676.1377700"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0216005"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009354"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"D. P. Dubhashi and A. Panconesi,\n                      Concentration of Measure for the Analysis of Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 2009.","DOI":"10.1017\/CBO9780511581274"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.03.004"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189991"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich, J.J. Tsay, D. E. Vengroff, and J. S. Vitter,\n                      External-memory computational geometry\n                      , in Proceedings of the 34th Annual IEEE Symposium on the Foundation of Computer Science (FOCS), 1993, pp. 714-723.","DOI":"10.1109\/SFCS.1993.366816"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.09.016"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/0215021"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/090753620"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.12.007"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/12089702X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:51:15Z","timestamp":1787338275000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/12089702X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/12089702X"],"URL":"https:\/\/doi.org\/10.1137\/12089702x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}