Largest and smallest area triangles on imprecise points

•Maximizing the largest triangle can be done in O(n2) time (or in O(nlog⁡n) time for unit segments).•Minimizing the largest triangle can be done in O(n4) time.•Maximizing the smallest triangle is NP-hard.•Minimizing the smallest triangle can be done in O(n2) time.•We also discuss to what extent our...

Full description

Saved in:
Bibliographic Details
Published in:Computational geometry : theory and applications 2021-04, Vol.95, p.101742, Article 101742
Main Authors: Keikha, Vahideh, Löffler, Maarten, Mohades, Ali
Format: Article
Language:English
Subjects:
Computational geometry
k-gon
Maximum area triangle
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•Maximizing the largest triangle can be done in O(n2) time (or in O(nlog⁡n) time for unit segments).•Minimizing the largest triangle can be done in O(n4) time.•Maximizing the smallest triangle is NP-hard.•Minimizing the smallest triangle can be done in O(n2) time.•We also discuss to what extent our results can be generalized to polygons with k>3 sides. 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(n2) time (or in O(nlog⁡n) time for unit segments); minimizing the largest triangle can be done in O(n4) time; maximizing the smallest triangle is NP-hard; but minimizing the smallest triangle can be done in O(n2) time. We also discuss to what extent our results can be generalized to polygons with k>3 sides.
ISSN:0925-7721
DOI:10.1016/j.comgeo.2020.101742