Largest and Smallest Area Triangles on Imprecise Points

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Largest and Smallest Area Triangles on Imprecise Points

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Largest and Smallest Area Triangles on Imprecise Points

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Strukturální vlastnosti viditelnosti terénů a Voroného diagramů nejvzdálenější barvy</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Computational Geometry-Theory and Applications

ISSN

0925-7721

e-ISSN

1879-081X

Svazek periodika

95

Číslo periodika v rámci svazku

April 2021

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

21

Strana od-do

101742

Kód UT WoS článku

000674250600007

EID výsledku v databázi Scopus

2-s2.0-85098725460