2026-07-21T20:26:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26038 2026-06-23T13:18:27Z ddc:004 open_access

On the Fragile Complexity of Geometric Algorithms Aronov, Boris Goswami, Mayank Iacono, John Ramesh, Indu Fragile complexity convex hull maxima closest pair algorithmic complexity Surprisingly, the question of bounding the maximum number of operations undergone by each individual element in an algorithm - known as the fragile complexity of the algorithm - has not received much attention. In a foundational paper, Afshani et al. (2019) developed the concept of fragility and explored classic problems such as sorting and selection from this perspective. Motivated by a suggestion for future research by Afshani et al., we initiate a study of fragile complexity in computational geometry. We obtain bounds on several time-honored questions in 2D such as computing the maxima, closest pair, convex hull, triangulation, and approximate Euclidean Minimum Spanning Tree (apx-EMST). Our algorithms for the maxima, convex hull, and triangulation problems are competitive with the classical algorithms in terms of worst-case runtime and guarantee polylogarithmic fragility. We present an O(nlog²n) time algorithm that returns a 1.0125-apx-EMST and achieves O(log² n) fragility, thus matching the best known performance up to polylogarithmic factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boris Aronov and Mayank Goswami and John Iacono and Indu Ramesh 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.2 urn:nbn:de:0030-drops-260386 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.2 eng https://creativecommons.org/licenses/by/4.0/legalcode