2024/11/07 by Van Der Hoog, Ivor, Kostitsyna, Irina, Löffler, Maarten +1
paper · doi:10.20382/jocg.v15i1a6
In this paper we study how to efficiently order a set of imprecise points. In one dimension, the order of a set of points is their sorted order from low to high. A set of imprecise points in the preprocessing model consists of a set of n uncertainty regions R = \R1, R2, … Rn \ and a set of n points P = \ p1, p2, … pn\ such that for every Ri ∈ R there is an associated point pi ∈ P with pi ∈ P. In one dimension, the set R is a set of intervals which induces a partial order such that the total order of the underlying true points P extends that partial order. We show how to preprocess the partial order induced by R, such that given the point set P we can uncover the underlying total order in uncertainty-region optimal time. Specifically, we parametrize the degree of overlap by the intervals with a measure we call the ambiguity of the set R and we show that the ambiguity of R is a lower bound for the time required to sort the points P. This paper can be seen as a geometric variant of sorting under partial information, which is a well-studied topic within computer science.