Search Results

Documents authored by Jallu, Ramesh K.

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.18
Half-Guarding Weakly-Visible Polygons and Terrains

Authors: Nandhana Duraisamy, Hannah Miller Hillberg, Ramesh K. Jallu, Erik Krohn, Anil Maheshwari, Subhas C. Nandy, and Alex Pahlow

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
We consider a variant of the art gallery problem where all guards are limited to seeing 180degree. Guards that can only see in one direction are called half-guards. We give a polynomial time approximation scheme for vertex guarding the vertices of a weakly-visible polygon with half-guards. We extend this to vertex guarding the boundary of a weakly-visible polygon with half-guards. We also show NP-hardness for vertex guarding a weakly-visible polygon with half-guards. Lastly, we show that the orientation of half-guards is critical in terrain guarding. Depending on the orientation of the half-guards, the problem is either very easy (polynomial time solvable) or very hard (NP-hard).
Cite as

Nandhana Duraisamy, Hannah Miller Hillberg, Ramesh K. Jallu, Erik Krohn, Anil Maheshwari, Subhas C. Nandy, and Alex Pahlow. Half-Guarding Weakly-Visible Polygons and Terrains. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{duraisamy_et_al:LIPIcs.FSTTCS.2022.18,
  author =	{Duraisamy, Nandhana and Hillberg, Hannah Miller and Jallu, Ramesh K. and Krohn, Erik and Maheshwari, Anil and Nandy, Subhas C. and Pahlow, Alex},
  title =	{{Half-Guarding Weakly-Visible Polygons and Terrains}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.18},
  URN =		{urn:nbn:de:0030-drops-174103},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.18},
  annote =	{Keywords: Art Gallery Problem, Approximation Algorithm, NP-Hardness, Monotone Polygons, Half-Guards}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.10
Terrain Prickliness: Theoretical Grounds for High Complexity Viewsheds

Authors: Ankush Acharyya, Ramesh K. Jallu, Maarten Löffler, Gert G.T. Meijer, Maria Saumell, Rodrigo I. Silveira, and Frank Staals

Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II

Abstract
An important task in terrain analysis is computing viewsheds. A viewshed is the union of all the parts of the terrain that are visible from a given viewpoint or set of viewpoints. The complexity of a viewshed can vary significantly depending on the terrain topography and the viewpoint position. In this work we study a new topographic attribute, the prickliness, that measures the number of local maxima in a terrain from all possible angles of view. We show that the prickliness effectively captures the potential of terrains to have high complexity viewsheds. We present near-optimal algorithms to compute it for TIN terrains, and efficient approximate algorithms for raster DEMs. We validate the usefulness of the prickliness attribute with experiments in a large set of real terrains.
Cite as

Ankush Acharyya, Ramesh K. Jallu, Maarten Löffler, Gert G.T. Meijer, Maria Saumell, Rodrigo I. Silveira, and Frank Staals. Terrain Prickliness: Theoretical Grounds for High Complexity Viewsheds. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{acharyya_et_al:LIPIcs.GIScience.2021.II.10,
  author =	{Acharyya, Ankush and Jallu, Ramesh K. and L\"{o}ffler, Maarten and Meijer, Gert G.T. and Saumell, Maria and Silveira, Rodrigo I. and Staals, Frank},
  title =	{{Terrain Prickliness: Theoretical Grounds for High Complexity Viewsheds}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.10},
  URN =		{urn:nbn:de:0030-drops-147697},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.10},
  annote =	{Keywords: Digital elevation model, Triangulated irregular network, Viewshed complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact