Sorting under partial (interval order) information.

In this paper we study how to efficiently order a set of imprecise points. Inone dimension, the order of a set of points is their sorted order from low to high. A setof imprecise points in the preprocessing model consists of a set ofnuncertainty regionsR={R1,R2,...Rn}and a set ofnpointsP={p1,p2,...pn}such that for everyRi∈ Rthere is an associated pointpi∈P. In one dimension, the setRis a set of intervals whichinduces a partial order such that the total order of the underlying true pointsPextends thatpartial order. We show how to preprocess the partial order induced byR, such that giventhe point setPwe can uncover the underlying total order in uncertainty-region optimaltime. Specifically, we parametrize the degree of overlap by the intervals with a measure wecall theambiguityof the setRand we show that the ambiguity ofRis a lower bound forthe time required to sort the pointsP. This paper can be seen as a geometric variant ofsorting under partial information, which is a well-studied topic within computer science