Guarding a 1.5D Terrain with Imprecise Viewpoints

Vahideh Keikha; Maarten Löffler; Maria Saumell; Pavel Valtr

doi:10.1007/978-3-031-98740-3_1

Guarding a 1.5D Terrain with Imprecise Viewpoints

Vahideh Keikha, Maarten Löffler, Maria Saumell^*, Pavel Valtr

^*Corresponding author for this work

Sub Geometric Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

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(n³) time.

Original language	English
Title of host publication	Combinatorial Algorithms - 36th International Workshop, IWOCA 2025, Proceedings
Editors	Henning Fernau, Binhai Zhu
Publisher	Springer
Pages	3-16
Number of pages	14
ISBN (Electronic)	978-3-031-98740-3
ISBN (Print)	978-3-031-98739-7
DOIs	https://doi.org/10.1007/978-3-031-98740-3_1
Publication status	Published - 18 Jul 2025
Event	36th International Workshop on Combinatorial Algorithms, IWOCA 2025 - Bozeman, United States Duration: 21 Jul 2025 → 24 Jul 2025

Publication series

Name	Lecture Notes in Computer Science
Volume	15885 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	36th International Workshop on Combinatorial Algorithms, IWOCA 2025
Country/Territory	United States
City	Bozeman
Period	21/07/25 → 24/07/25

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

Keywords

1.5D terrain
Data imprecision
Multiple Viewpoints
Visibility

Access to Document

10.1007/978-3-031-98740-3_1

Cite this

@inproceedings{3122aa4f3dca41d4ad34d4a83607aa80,

title = "Guarding a 1.5D Terrain with Imprecise Viewpoints",

abstract = "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.",

keywords = "1.5D terrain, Data imprecision, Multiple Viewpoints, Visibility",

author = "Vahideh Keikha and Maarten L{\"o}ffler and Maria Saumell and Pavel Valtr",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 36th International Workshop on Combinatorial Algorithms, IWOCA 2025 ; Conference date: 21-07-2025 Through 24-07-2025",

year = "2025",

month = jul,

day = "18",

doi = "10.1007/978-3-031-98740-3\_1",

language = "English",

isbn = "978-3-031-98739-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "3--16",

editor = "Henning Fernau and Binhai Zhu",

booktitle = "Combinatorial Algorithms - 36th International Workshop, IWOCA 2025, Proceedings",

}

Keikha, V, Löffler, M, Saumell, M & Valtr, P 2025, Guarding a 1.5D Terrain with Imprecise Viewpoints. in H Fernau & B Zhu (eds), Combinatorial Algorithms - 36th International Workshop, IWOCA 2025, Proceedings. Lecture Notes in Computer Science, vol. 15885 LNCS, Springer, pp. 3-16, 36th International Workshop on Combinatorial Algorithms, IWOCA 2025, Bozeman, United States, 21/07/25. https://doi.org/10.1007/978-3-031-98740-3_1

Guarding a 1.5D Terrain with Imprecise Viewpoints. / Keikha, Vahideh; Löffler, Maarten; Saumell, Maria et al.
Combinatorial Algorithms - 36th International Workshop, IWOCA 2025, Proceedings. ed. / Henning Fernau; Binhai Zhu. Springer, 2025. p. 3-16 (Lecture Notes in Computer Science; Vol. 15885 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Guarding a 1.5D Terrain with Imprecise Viewpoints

AU - Keikha, Vahideh

AU - Löffler, Maarten

AU - Saumell, Maria

AU - Valtr, Pavel

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025/7/18

Y1 - 2025/7/18

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

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

KW - 1.5D terrain

KW - Data imprecision

KW - Multiple Viewpoints

KW - Visibility

UR - https://www.scopus.com/pages/publications/105011991694

U2 - 10.1007/978-3-031-98740-3_1

DO - 10.1007/978-3-031-98740-3_1

M3 - Conference contribution

AN - SCOPUS:105011991694

SN - 978-3-031-98739-7

T3 - Lecture Notes in Computer Science

SP - 3

EP - 16

BT - Combinatorial Algorithms - 36th International Workshop, IWOCA 2025, Proceedings

A2 - Fernau, Henning

A2 - Zhu, Binhai

PB - Springer

T2 - 36th International Workshop on Combinatorial Algorithms, IWOCA 2025

Y2 - 21 July 2025 through 24 July 2025

ER -