Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness
David Eppstein, Michael T. Goodrich, Abraham M. Illickan, Claire A. To, Department of Computer Science, University of California, Irvine · 2025
Read Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness by David Eppstein, Michael T. Goodrich, Abraham M. Illickan, Claire A. To, Department of Computer Science, University of California, Irvine (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20489.txt.
Introduction
David Eppstein, Michael Goodrich, Abraham Illickan, and Claire To present a computing paper from 2025 on geometry algorithms. Some algorithms run faster when the input is partly sorted or has low disorder. Disorder can be measured by entropy, a score of how mixed the data is.
The authors define a new entropy measure based on how points split across ranges. Their measure covers past ones used for sorting and for geometry in one frame. They give simple algorithms for flat maxima, hulls in two and three dimensions, and some line-of-sight tasks. Each algorithm's run time tracks the new entropy of its input. Sorted inputs thus finish fast, while mixed inputs cost more. The work aims to make such adaptive methods easier to design.
Catalog record
| CREATOR | David Eppstein, Michael T. Goodrich, Abraham M. Illickan, Claire A. To, Department of Computer Science, University of California, Irvine |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20489
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness Thanks: This research was supported in part by NSF grant 2212129. David Eppstein, Michael T. Goodrich, Abraham M. Illickan, Claire A. To, Department of Computer Science, University of California, Irvine Abstract We study entropy-bounded computational geometry, that is, geometric algorithms whose running times depend on a given measure of the input entropy. Specifically, we introduce a measure that we call range-partition entropy , which unifies and subsumes previous definitions of entropy used for sorting problems and structural entropy used in computational geometry. We provide simple algorithms for several problems, including 2D maxima, 2D and 3D convex hulls, and some visibility problems, and we show that they have running times depending on the range-partition entropy. 1 Introduction Beyond worst-case algorithm design is directed at designing algorithms whose running time is asymptotically the best possible relative to some metric of the input instance [ 17 , 18 ] , and there has been considerable work done, for example, on instance-optimal sorting algorithms; see, e.g., [ 15 , 11 , 8 , 2 , 4 , 20 , 19 , 3 ] . Focusing on the sorting problem for a moment, let X=[x_{1},x_{2},\ldots,x_{n}] be an input sequence of distinct elements that come from a total order, and let \mathcal{R}=\{R_{1},R_{2},\ldots,R_{\rho(X)}\} be a division of X into a set of maximal increasing or decreasing runs (i.e., consecutive elements in X ). These previous papers define a type of entropy , \mathrm{H}({X}) , for a set of elements, X , divided into runs as follows [ 15 , 11 , 8 , 2 , 4 , 20 , 19 , 3 ] : \mathrm{H}({X})=-\sum_{i=1}^{\rho(X)}\left(\frac{|R_{i}|}{n}\right)\log\left(\frac{|R_{i}|}{n}\right). Sequential comparison-based sorting has a runtime lower bound of \Omega(n(1+\mathrm{H}({X}))) , and many instance-optimal sorting algorithms have running time O(n(1+\mathrm{H}({X}))) , which can be as small as O(n) depending on the input instance. For example, Auger, Jugé, Nicaud, and Pivoteau [ 2 ] show that the popular TimSort algorithm has this time, and similarly efficient stack-based mergesort algorithms have been given by Munro and Wild [ 15 ] , Jugé [ 11 ] , Gelling, Nebel, Smith, and Wild [ 8 ] , Buss and Knop’ [ 4 ] , Takaoka [ 20 ] , and Barbay and Navarro [ 3 ] . At CCCG’24, Schou and Wang introduce PersiSort [ 19 ] , which also has this running time. Still, we are not aware of any work on geometric problems beyond sorting that concern instance optimality with respect to run-based entropy. Instead, given an input, S , to a geometric problem, such as convex hull or maxima set, Afshani, Barbay, and Chan [ 1 ] introduce the structural entropy , \mathrm{H}(S) for S , and they provide algorithms that run in O(n(1+\mathrm{H}(S))) time for several such problems, where n is the size of the input, including 2D maxima and 2D and 3D convex hulls. In contrast to the entropy used for the sorting problem, however, structural entropy explicitly ignores any near-sortedness in the input, such as can occur, e.g., with convex polygons or monotone polygonal chains. Our Results. In this paper, we introduce a unification of the entropy used for sorting and the structural entropy of Afshani et al. [ 1 ] , which we call range-partition entropy . This unification applied even for problems that do not have obvious structural entropy: for instance, in the visibility and lower-envelope problems we study, range-partition entropy equals the entropy of an embedded sorting problem. In other cases, such as for 3D convex hulls, sortedness provides no obvious advantage, and case range-partition entropy reduces to the structural entropy of Afshani et al . We provide simple algorithms whose running times depend on the range-partiton entropy, \mathrm{H}(S) , of an input set of points, S . For example, we give algorithms for computing maxima sets and convex hulls for n points in the plane in O(n(1+\mathrm{H}(S))) time. These algorithms perform no worse than any other algorithm for any input on their respective worst permutations, while also taking advantage of sortedness in the input. We also show how to adapt any instance-optimal natural mergesort to compute the lower envelope of monotone polygonal chains or the visibility polygon of a point inside a convex polygon with convex holes in time that depends on the range-partition entropy. In addition, we give a simple randomized algorithm for computing the convex hull of n points in \mathbf{R}^{3} and show its expected running time to be O(n(1+\mathrm{H}(S))) . 2 Range-Partition Entropy Let S=(p_{1},p_{2},\ldots,p_{n}) be the set of n points in \mathbf{R}^{d} input in this given order, for constant d\geq 1 . Define a range partition of S to be a set, \Pi=\{(S_{1},R_{1}),(S_{2},R_{2}),\ldots,(S_{t},R_{t})\} , such that 1. The S_{i} ’s form a partition of S , i.e., S=\bigcup_{i=1}^{t}S_{i} and S_{i}\cap S_{j}=\emptyset for i\not=j . 2. The R_{i} ’s are geometric ranges , such as intervals in \mathbf{R} , axis-aligned rectangles in \mathbf{R}^{2} , triangles in \mathbf{R}^{2} , or tetrahedra in \mathbf{R}^{3} , such that the set, S_{i} , is contained in the range, R_{i} . For example, if S is a set of points in \mathbf{R}^{2} , then \Pi could be a partition of S into subsets contained in a set of axis-aligned rectangles, which form the ranges. Given a sequence, S , of points in \mathbf{R}^{d} , and a range partition, \Pi=\{(S_{1},R_{1}),\ldots,(S_{t},R_{t})\} , for S , we say that \Pi is respectful if it satisfies the following constraints: 1. For each i=1,2,\ldots,t , (S_{i},R_{i}) satisfies a given local property , which depends only on S_{i} and R_{i} . 2. For each i=1,2,\ldots,t , (S_{i},R_{i}) satisfies a given global compatibility property, which can depend on the other pairs, (S_{j},R_{j}) , for j\not=i . Given a set, S , of n points in \mathbf{R}^{d} , the entropy , \mathrm{H}(\Pi) , of a partition, \Pi=\{(S_{1},R_{1}),\ldots,(S_{t},R_{t})\} , of S , is \mathrm{H}({\Pi})=-\sum_{i=1}^{t}\left(\frac{|S_{i}|}{n}\right)\log\left(\frac{|S_{i}|}{n}\right). The range-partition entropy , \mathrm{H}(S) , of S is the minimum \mathrm{H}(\Pi) over all respectful partitions, \Pi . We reformulate the sorting problem in this framework by considering the input sequence, S=(x_{1},x_{2},\ldots,x_{n}) , to be points in \mathbf{R} , and we define a partition, \Pi=\{(S_{1},R_{1}),\ldots,(S_{t},R_{t})\} , where each range, R_{i} , is an interval, [a,b]\subset\mathbf{R} . In this case, the local property of each (S_{i},R_{i}) is that S_{i} is a consecutive subsequence of elements in S given in sorted order, and the global property is that the R_{i} ranges are disjoint, i.e., R_{i}\cap R_{j}=\emptyset for i\not=j . Accordingly, the minimum entropy, \mathrm{H}(\Pi) , for all respectful partitions, \Pi , is determined by a partition of the input sequence into maximal non-decreasing or non-increasing runs. Thus, our framework subsumes the notion of entropy used for the sorting problem. Also, as we discuss in more detail in subsequent sections, it also subsumes the structural entropy introduced by Afshani et al. [ 1 ] . 3 2D Maxima Set The problem we study in this section is to find the maxima set of a given set of points in the plane, where a point is considered maximal if no other point dominates it, having both greater x - and y -coordinates. Our algorithm for this problem is a simple a variant of Kirkpatrick and Seidel’s “marriage-before-conquest” method