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 .
Assume we are given a set of parallel line segments in the plane , and we wish to place a point on each line segment such that the resulting point set maximizes or minimizes the area of the largest or smallest triangle in the set. We analyze the complexity of the four resulting computational problems, and we show that three of them admit polynomial-time algorithms, while the fourth is NP-hard. Specifically, we show that maximizing the largest triangle can be done in O(n ^2) time (or in O(n \log n) time for unit segments); minimizing the largest triangle can be done in O(n^2 \log n) time ; maximizing the smallest triangle is NP-hard ; but minimizing the smallest triangle can be done in O(n^2) time. We also discuss to what extent our results can be generalized to polygons with k>3 sides .
R
In this paper we study the following problem: we
Assume we
D
imprecise points modeled as
A
in the plane
R
/minimizes the size
or minimizes the area
R
/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
or smallest triangle in the set. We analyze the complexity of the four resulting computational problems, and we show that three of them admit polynomial-time algorithms, while the fourth is NP-hard. Specifically, we show that maximizing the largest
R
found
done
R
\log n) time , and for line segments of arbitrary length the problem can be solved
^2) time (or
R
^2) time . Also, we show that the smallest largest-area
\log n) time for unit segments); minimizing the largest
R
found
done
R
. As for finding smallest-area triangles, we show that finding the largest smallest-area
; maximizing the smallest
R
, but that the smallest possible area triangle for a set of arbitrary length parallel line segments can be found
; but minimizing the smallest triangle can be done
R
Finally, we
We also
R
larger values of k
polygons with k>3 sides