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(nlogn) time, and for line segments of arbitrary length the problem can be solved in O(n2) time. We also show that the smallest possible area triangle for a set of arbitrary length parallel line segments can be found in O(n2) 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