Instance-Optimal Imprecise Convex Hull
Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, Sampson Wong · 2025
Read Instance-Optimal Imprecise Convex Hull by Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, Sampson Wong (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-2504-02611.txt.
Introduction
Survey data often locates points only roughly, inside a region rather than at a spot. Five authors tackle a classic task under that handicap: find the convex hull, the rubber-band outline, of the true points, while paying for each precise measurement you choose to make. Earlier work optimized either the number of measurements or the computing time, never both.
Their algorithm is optimal on both counts at once for an input of polygon regions. It makes only the minimum number of measurements any method could need for that particular input. It also decides each next measurement in polylogarithmic time, an exponential speedup per step over rivals that match its frugality. Extensions cover many-sided polygons and disjoint disks of bounded size range. The result matters wherever precision is expensive, from sensors to geographic data.
Catalog record
| CREATOR | Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, Sampson Wong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-02611
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Instance-Optimal Imprecise Convex Hull Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, Sampson Wong Abstract Imprecise measurements of a point set P = ( p 1 , … , p n ) P=(p_{1},\ldots,p_{n}) can be modelled by a family of regions F = ( R 1 , … , R n ) F=(R_{1},\ldots,R_{n}) , where each imprecise region R i ∈ F R_{i}\in F contains a unique point p i ∈ P p_{i}\in P . A retrieval models an accurate measurement by replacing an imprecise region R i R_{i} with its corresponding point p i p_{i} . We construct the convex hull of an imprecise point set in the plane, by determining the cyclic ordering of the convex hull vertices of P P as efficiently as possible. Efficiency is interpreted in two ways: (i) minimising the number of retrievals, and (ii) the computation time to determine the set of regions that must be retrieved. Previous works focused on only one of these two aspects: either minimising retrievals or optimising algorithmic runtime. Our contribution is the first to simultaneously achieve both. Let r ( F , P ) r(F,P) denote the minimal number of retrievals required by any algorithm to determine the convex hull of P P for a given instance ( F , P ) (F,P) . For a family F F of n n constant-complexity polygons, our main result is a reconstruction algorithm that performs Θ ( r ( F , P ) ) \Theta(r(F,P)) retrievals in O ( r ( F , P ) log 3 n ) O(r(F,P)\log^{3}n) time. Compared to previous approaches that achieve optimal retrieval counts, we improve the runtime per retrieval from polynomial to polylogarithmic. We extend the generality of previous results to simple k k -gons, to pairwise disjoint disks with radii in [ 1 , k ] [1,k] , and to unit disks where at most k k disks overlap in a single point. Our runtime scales linearly with k k . IT University of Copenhagen, [email protected] IT University of Copenhagen, [email protected]://orcid.org/0009-0006-2624-0231This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987 IT University of Copenhagen, [email protected] IT University Copenhagen, [email protected] https://orcid.org/0009-0005-6838-2628 University of Copenhagen, [email protected]://orcid.org/0000-0003-3803-3804This project has recieved funding from the European Union’s Skłodowska-Curie Actions Postdoctoral Fellowship grant agreement No 101146276. ccs Theory of computation Computational Geometry keywords convex hull, imprecise geometry preprocessing model, partial information † † funding: This research is supported by the Carlsberg Foundation Fellowship CF21-0302 “Graph Algorithms with Geometric Applications” and the VILLUM Foundation grants VIL37507 “VIL37507 Recomputations for Changeful Problems”. † † runningauthor: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, Sampson Wong † † editors: Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman † † event-title: 33rd Annual European Symposium on Algorithms (ESA 2025) † † event-shorttitle: ESA 2025 † † event-acronym: ESA † † year: 2025 † † event-date: September 15–17, 2025 † † event-location: Warsaw, Poland † † series-volume: 351 † † articleno: 23 † † copyright: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, Sampson Wong 1 Introduction Imprecision is inherent in real-world data. It arises from rounding errors in floating-point computations, inaccuracies in measurement, and delayed sampling in GPS devices. In many scenarios, imprecise data can be refined at a cost by computing exact values or by taking additional samples. This is formalised in the model of imprecise geometry introduced by Held and Mitchell [ 14 ] , and studied further in [ 9 , 14 , 26 , 10 , 11 , 20 , 18 ] . Imprecise geometry. An imprecise point set [ 14 ] is defined as a family of regions F=(R_{1},\ldots,R_{n}) , where each region R_{i} contains a unique but unknown point p_{i} . A realisation P\sim F is a sequence P=(p_{1},\ldots,p_{n}) where p_{i}\in R_{i} . An input instance is a pair (F,P) . A retrieval operation reveals the precise location of a point p_{i} , replacing R_{i} with p_{i} . Let F\hskip-1.42271pt\odot_{\hskip-1.42271pt\textit{P}}\hskip-0.85355ptB denote the family F after retrieving all R_{i}\in B , where B\subset F . The aim of a reconstruction algorithm is to identify a subset B\subset F such that for all realisations P_{1},P_{2}\sim F\hskip-1.42271pt\odot_{\hskip-1.42271pt\textit{P}}\hskip-0.85355ptB , the algorithm’s output (e.g., the cyclic order of the region indices of the points around the convex hull) is identical for P_{1} and P_{2} . Figure 1 illustrates an example. After retrieving the subset B=\{R_{3},R_{4}\} , the cycling ordering of the convex hull vertices is identically (p_{1},p_{3},p_{2},p_{4}) for all realisations of F\hskip-1.42271pt\odot_{\hskip-1.42271pt\textit{P}}\hskip-0.85355ptB . We evaluate reconstruction algorithms by three criteria: the preprocessing time, the total number of retrievals, and the running time per retrieval. Next, we consider instance-optimal algorithms, which minimise the total number of retrievals in the strictest sense. Figure 1: (a) A family of regions F=R_{1},\ldots,R_{5} and a sequence P=(p_{1},\ldots,p_{5}) with P\sim F . (b) If we retrieve R_{3} and R_{4} to obtain F^{\prime} then for all P^{\prime}\sim F^{\prime} the convex hull equals (p_{1},p_{3},p_{2},p_{4}) . Note that if p_{3} would lie in R_{2}\cap R_{3} instead, then retrieving only R_{3} and R_{4} does not suffice. Worst-case results. Many geometric problems have been studied in imprecise geometry, including Delaunay triangulations [ 9 , 14 , 20 , 26 ] , convex hulls [ 10 , 11 ] , Gabriel graphs [ 20 ] , and onion decompositions [ 18 ] . For these geometric problems, it is known that any reconstruction algorithm must, in the worst case, use \Omega(n) retrievals. Most of the existing algorithms assume that the regions in F are pairwise disjoint unit disks [ 9 , 14 , 20 , 26 , 10 , 18 ] . Under these assumptions, deterministic worst-case optimal algorithms exist with O(n\log n) preprocessing time, O(n) retrievals, and O(n) reconstruction time. Ezra and Mulzer [ 11 ] allow F to consist of arbitrary lines and reconstruct the convex hull using O(n) retrievals and O(n\cdot\alpha(n)) expected time where \alpha(n) denotes the inverse Ackermann function. Buchin, Löffler, Morin and Mulzer [ 4 ] permit overlapping unit disks of ply k (i.e., at most k disks intersect each point in the plane). We summarize these results in the top three rows of Table 1 . Instance-optimality. In many instances, worst case bounds are overly pessimistic. Intuitively, an algorithm is instance-optimal if, for every input (F,P) , no other algorithm performs better on that instance. Constructing instance-optimal algorithms is challenging, as they must match every alternative algorithm, including those tailored for specific instances. Afshani, Barbay, and Chan [ 1 ] proved that, for many geometric problems including constructing the convex hull, instance-optimal reconstruction time is unachievable. Likewise, it is easy to see that instance-optimality in the number of retrievals cannot be guaranteed in general: E.g., let F consist of two overlapping intervals R_{1} and R_{2} in \mathbb{R} , with R_{1}\setminus R_{2}\neq\emptyset and R_{2}\setminus R_{1}\neq\emptyset . Define P_{1} with p_{1}\in R_{1}\setminus R_{2} and p_{2}\in R_{1}\cap R_{2} , and P_{2} with p_{1}\in R_{1}\cap R_{2} and p_{2}\in R_{2}\setminus R_{1} . In (F,P_{1}) , retrieving R_{1} suffices; in (F,P_{2}) , retrieving R_{2} suffices. No algorithm can distinguish between the two