Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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