On Voronoi visibility maps of 1.5D terrains with multiple viewpoints
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F23%3A00567920" target="_blank" >RIV/67985807:_____/23:00567920 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/68407700:21240/23:00366414
Výsledek na webu
<a href="https://doi.org/10.1016/j.ipl.2023.106362" target="_blank" >https://doi.org/10.1016/j.ipl.2023.106362</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ipl.2023.106362" target="_blank" >10.1016/j.ipl.2023.106362</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On Voronoi visibility maps of 1.5D terrains with multiple viewpoints
Popis výsledku v původním jazyce
Given an n-vertex 1.5D terrain T and a set P of m < n viewpoints, the Voronoi visibility map VorVis(T,P) is a partitioning of T into regions such that each region is assigned to the closest (in Euclidean distance) visible viewpoint. The colored visibility map ColVis(T, P) is a partitioning of T into regions that have the same set of visible viewpoints. In this paper, we propose an algorithm to compute VorVis(T,P) that runs in O(n + (m2 + kc) log n) time, where kc and kv denote the total complexity of ColVis(T, P) and VorVis(T, P), respectively. This improves upon a previous algorithm for this problem. We also generalize our algorithm to higher order Voronoi visibility maps, and to Voronoi visibility maps with respect to other distances. Finally, we prove bounds relating kv to kc, and we show an application of our algorithm to a problem on limited range of sight.
Název v anglickém jazyce
On Voronoi visibility maps of 1.5D terrains with multiple viewpoints
Popis výsledku anglicky
Given an n-vertex 1.5D terrain T and a set P of m < n viewpoints, the Voronoi visibility map VorVis(T,P) is a partitioning of T into regions such that each region is assigned to the closest (in Euclidean distance) visible viewpoint. The colored visibility map ColVis(T, P) is a partitioning of T into regions that have the same set of visible viewpoints. In this paper, we propose an algorithm to compute VorVis(T,P) that runs in O(n + (m2 + kc) log n) time, where kc and kv denote the total complexity of ColVis(T, P) and VorVis(T, P), respectively. This improves upon a previous algorithm for this problem. We also generalize our algorithm to higher order Voronoi visibility maps, and to Voronoi visibility maps with respect to other distances. Finally, we prove bounds relating kv to kc, and we show an application of our algorithm to a problem on limited range of sight.
Klasifikace
Druh
J<sub>imp</sub> - Č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)
Návaznosti výsledku
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
Ostatní
Rok uplatnění
2023
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ů
Údaje specifické pro druh výsledku
Název periodika
Information Processing Letters
ISSN
0020-0190
e-ISSN
1872-6119
Svazek periodika
181
Číslo periodika v rámci svazku
March 2023
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
8
Strana od-do
106362
Kód UT WoS článku
000978674300001
EID výsledku v databázi Scopus
2-s2.0-85146837975