Guarding a 1.5D Terrain with Imprecise Viewpoints

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F25%3A00384580" target="_blank" >RIV/68407700:21240/25:00384580 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-98740-3_1" target="_blank" >https://doi.org/10.1007/978-3-031-98740-3_1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-98740-3_1" target="_blank" >10.1007/978-3-031-98740-3_1</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Guarding a 1.5D Terrain with Imprecise Viewpoints

Popis výsledku v původním jazyce

Given an n-vertex 1.5D terrain T and a set of m edges of T, we study the problem of placing one viewpoint on each edge so that the total length of the visible portions of the terrain is maximized. We present an O(n+m*log m) time (1/2)-approximation algorithm for the general problem, and polynomial-time algorithms for the cases m=1 and m=2. Additionally, we show that the problem of computing a point on T maximizing the visible portion of T can be solved in O(n^3) time.

Název v anglickém jazyce

Guarding a 1.5D Terrain with Imprecise Viewpoints

Popis výsledku anglicky

Given an n-vertex 1.5D terrain T and a set of m edges of T, we study the problem of placing one viewpoint on each edge so that the total length of the visible portions of the terrain is maximized. We present an O(n+m*log m) time (1/2)-approximation algorithm for the general problem, and polynomial-time algorithms for the cases m=1 and m=2. Additionally, we show that the problem of computing a point on T maximizing the visible portion of T can be solved in O(n^3) time.

Druh

D - Stať ve sborníku

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/GX23-04949X" target="_blank" >GX23-04949X: Stěžejní otázky diskrétní geometrie</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

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 statě ve sborníku

36th International Workshop on Combinatorial Algorithms (IWOCA 2025)

ISBN

978-3-031-98740-3

ISSN

1611-3349

e-ISSN

1611-3349

Počet stran výsledku

14

Strana od-do

3-16

Název nakladatele

Springer

Místo vydání

Wien

Místo konání akce

Bozeman

Datum konání akce

21. 7. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001596018900001