Largest and Smallest Area Triangles on a Given Set of Imprecise Points.

In this paper we study the following problem: we are given a set of imprecise points modeled as parallel line segments, and we wish to place a point on each line segment such that the resulting point set maximizes/minimizes the size of the largest/smallest area $k$-gon. We first study the problem for the case $k=3$. We show that for a given set of parallel line segments of equal length the largest possible area triangle can be found in $O(n \log n)$ time, and for line segments of arbitrary length the problem can be solved in $O(n^2)$ time. Also, we show that the smallest largest-area triangle can be found in $O(n^2 \log n)$ time. As for finding smallest-area triangles, we show that finding the largest smallest-area triangle is NP-hard, but that the smallest possible area triangle for a set of arbitrary length parallel line segments can be found in $O(n^2)$ time. Finally, we discuss to what extent our results can be generalized to larger values of $k$.