## 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 three points in
different regions such that the resulting triangle has the largest or smallest possible area. We first present some facts about this problem in the context of imprecise points, then we show that for a given set of 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. We also show that the smallest possible area triangle for a set of arbitrary length parallel line segments can be found in *O*(*n*^{2}) time.

keywords: Computational Geometry, Data Imprecision

### Workshop or Poster (weakly reviewed)

Ali Mohades, Maarten Löffler, Vahideh Keikha

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

Proc. 33rd European Workshop on Computational Geometry

125–128, 2017

back to list