Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914185126871040 |
|---|---|
| author | van der Hoog, Ivor Rotenberg, Eva Rutschmann, Daniel |
| author_facet | van der Hoog, Ivor Rotenberg, Eva Rutschmann, Daniel |
| contents | TimSort is a well-established sorting algorithm whose running time depends on how sorted the input already is. Recently, Eppstein, Goodrich, Illickan, and To designed algorithms inspired by TimSort for Pareto front, planar convex hull, and two other problems. For each of these problems, they define a Range Partition Entropy; a function $H$ mapping lists $I$ that store $n$ points to a number between $0$ and $\log n$. Their algorithms have, for each list of points $I$, a running time of $O(n(1 + H(I)))$.
In this paper, we provide matching lower bounds for the Pareto front and convex hull algorithms by Eppstein, Goodrich, Illickan, and To. In particular, we show that their algorithm does not correspond to TimSort (or related stack-based MergeSort variants) but rather to a variant of QuickSort. From this, we derive an intuitive notion of universal optimality. We show comparison-based lower bounds that prove that the algorithms by Eppstein, Goodrich, Illickan and To are universally optimal under this notion of universal optimality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_06559 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull van der Hoog, Ivor Rotenberg, Eva Rutschmann, Daniel Computational Geometry Data Structures and Algorithms TimSort is a well-established sorting algorithm whose running time depends on how sorted the input already is. Recently, Eppstein, Goodrich, Illickan, and To designed algorithms inspired by TimSort for Pareto front, planar convex hull, and two other problems. For each of these problems, they define a Range Partition Entropy; a function $H$ mapping lists $I$ that store $n$ points to a number between $0$ and $\log n$. Their algorithms have, for each list of points $I$, a running time of $O(n(1 + H(I)))$. In this paper, we provide matching lower bounds for the Pareto front and convex hull algorithms by Eppstein, Goodrich, Illickan, and To. In particular, we show that their algorithm does not correspond to TimSort (or related stack-based MergeSort variants) but rather to a variant of QuickSort. From this, we derive an intuitive notion of universal optimality. We show comparison-based lower bounds that prove that the algorithms by Eppstein, Goodrich, Illickan and To are universally optimal under this notion of universal optimality. |
| title | Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.06559 |