In a certain robotics application, I encountered a problem in which we need to determine the order of positions of several robots on $\mathbb{R}$. Each measurement that we take of robot positions is subject to random errors beyond our control. I've formalised the algorithmic part of the problem as follows. This part has been reformulated as per D.W.'s comments.The positions of $n$ robots are given to us in a $3\times n$ array, each row being of the form $[i, A, \epsilon]$.This row states   that the position of the robot with id $i$ is uniformly distributed on the interval $A \pm \epsilon$.Problem : Output the most probable ordering (MPO) of the robot positions,or one such if this is non-unique.Example Input: $\begin{bmatrix} \mathrm{id} & A & \epsilon \\ \hline  1 & 1& 0.5 \\ 2& 1.5 & 2 \end{bmatrix}$. Associate the two robot positions with random variables $X_1$ and $X_2$. Note that the pair $(X_1,X_2)$ is uniform on the rectangle $[0.5,1.5] \times [-0.5,3.5]$.  The probability $p_1$ (resp. $p_2$) that $X_1\leq X_2$ (resp. $X_1 \geq X_2$) is the area of this rectangle below (resp. above) the line $x_1\leq x_2$. If $p_1 \leq p_2$, then the MPO is $[1,2]$ , else $[2,1]$. What data structure efficiently computes the MPO? I'm most interested in the range $n\in [10,1000]$.Simple idea that doesn't work (thanks to D.W.): When $n\geq 3$, the MPO isn't equal to the sorted order of the means $A_i$. For example, the input $(1, 0.4\pm0), (2,0.5\pm 0.5), (3,0.7 \pm 0)$ has the MPO $[2,1,3]$ and not $[1,2,3]$ as the $A$'s would have us think. One possible approach uses the Sweep Line algorithm. Think of a robot position as a rectangle corresponding to its uniform pdf. Compute all intersecting rectangles using the Priority Queue of the sweep line, and reorder them as per the probability calculation above. (It may be possible to reduce the $O(n^2)$ pairwise comparison of probabilities to $O(n \log n)$; I haven't checked this though.) Non-overlapping rectangles leave their ordering intact.Intuitively, large error bounds lead to long rectangles and potentially more overlaps, consequently increasing the running time. Likewise, small error bounds cause few overlaps, speeding up computations. This fact will be reflected in the sweep line.
Data structures for ordering noisy data
data structures;randomized algorithms;permutations