Name
Abstract | ||
|---|---|---|
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$. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Computational Geometry | Binary logarithm,Line segment,Discrete mathematics,Combinatorics,Parallel,Point set,Mathematics |
DocType | Volume | Citations |
Journal | abs/1712.08911 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vahideh Keikha | 1 | 1 | 2.85 |
| Maarten Löffler | 2 | 551 | 62.87 |
| Ali Mohades | 3 | 140 | 26.04 |