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%2F67985807%3A_____%2F25%3A00639507" target="_blank" >RIV/67985807:_____/25:00639507 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/25:10513729

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+mlogm) time 12-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(n3) 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+mlogm) time 12-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(n3) 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

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Combinatorial Algorithms. 36th International Workshop, IWOCA 2025 Proceedings

ISBN

978-3-031-98739-7

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

14

Strana od-do

3-16

Název nakladatele

Springer

Místo vydání

Cham

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