Largest and Smallest Area Triangles on Imprecise Points
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00536127" target="_blank" >RIV/67985807:_____/21:00536127 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.comgeo.2020.101742" target="_blank" >http://dx.doi.org/10.1016/j.comgeo.2020.101742</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.comgeo.2020.101742" target="_blank" >10.1016/j.comgeo.2020.101742</a>
Alternative languages
Result language
angličtina
Original language name
Largest and Smallest Area Triangles on Imprecise Points
Original language description
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(n log n) time for unit segments). Minimizing the largest triangle can be done in (O(n2 log n) 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Structural properties of visibility in terrains and farthest color Voronoi diagrams</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Computational Geometry-Theory and Applications
ISSN
0925-7721
e-ISSN
1879-081X
Volume of the periodical
95
Issue of the periodical within the volume
April 2021
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
21
Pages from-to
101742
UT code for WoS article
000674250600007
EID of the result in the Scopus database
2-s2.0-85098725460