More Web Proxy on the site http://driver.im/

research-article

Computing highly occluded paths on a terrain

Authors:

Thomas Mølhave,

Pankaj K. AgarwalAuthors Info & Claims

SIGSPATIAL'13: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Pages 14 - 23

https://doi.org/10.1145/2525314.2525363

Published: 05 November 2013 Publication History

Abstract

Understanding the locations of highly occluded paths on a terrain is an important GIS problem. In this paper we present a model and a fast algorithm for computing highly occluded paths on a terrain. It does not assume the observer locations to be known and yields a path likely to be occluded under a rational observer strategy. We present experimental results that examine several different observer strategies. The repeated visibility map computations necessary for our model is expedited using a fast algorithm for calculating approximate visibility maps that models the decrease in observational fidelity as distance increases. The algorithm computes a multiresolution approximate visibility map and makes use of a graphics processing unit (GPU) to speed up computation. We present experimental results on terrrain data sets with up to 144 million points.

References

[1]

P. K. Agarwal, L. Arge, and K. Yi, I/O-efficient batched union-find and its applications to terrain analysis, ACM Trans. Algorithms 7 (2011), Article 11.

Digital Library

[2]

L. Aleksandrov, H. Djidjev, A. Maheshwari, and J.-R. Sack, An approximation algorithm for computing shortest paths in weighted 3-d domains, Discr. Comput. Geom., 50 (2013), 124--184.

Digital Library

[3]

L. Aleksandrov, A. Maheshwari, and J.-R. Sack, Approximation algorithms for geometric shortest path problems, Proc. 32nd ACM Sypos. Theory. Comput., 2000, pp. 286--295.

Digital Library

[4]

C. Cai and S. Ferrari, Information-driven sensor path planning by approximate cell decomposition, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 39 (2009), 672--689.

Digital Library

[5]

J. Chen and Y. Han, Shortest paths on a polyhedron, Int. J. Comput. Geometry Appl., 6 (1996), 127--144.

[6]

M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications, Springer, 2010.

Digital Library

[7]

H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, American Mathematical Society, 2010.

[8]

W. R. Franklin, M. Inanc, Z. Xie, D. M. Tracy, B. Cutler, and M. V. A. Andrade, Smugglers and border guards: the geostar project at rpi, Proc. ACM-GIS, 2007, pp. 30:1--8.

Digital Library

[9]

M. Hielsberg, R. Tsai, P. Guo, and C. Chen, Visibility-based urban exploration and learning using point clouds, Proc. IEEE/RSJ Intl. Conf. Intell. Robots Sys., 2013.

[10]

K. Klein and S. Suri, Capture bounds for visibility-based pursuit evasion, Proc. 29th Sympos. Comput. Geom., 2013, pp. 329--338.

Digital Library

[11]

Y. Landa and R. Tsai, Visibility of point clouds and exploratory path planning in unknown environments, Commun. Math. Sci., 6 (2008), 881--913.

[12]

S. LaValle, Planning Algorithms, Cambridge University Press, 2006.

[13]

J. Lee and D. Stucky, On applying viewshed analysis for determining least-cost paths on digital elevation models, Intl. J. Geog. Info. Sci., 12 (1998), 891--905.

[14]

M. Lu, J. Zhang, P. Lv, and Z. Fan, Max/min path visual coverage problems in raster terrain, Computer-Aided Design and Computer Graphics, 2007, pp. 497--500.

[15]

D. Luebke, B. Watson, J. D. Cohen, M. Reddy, and A. Varshney, Level of Detail for 3D Graphics, Elsevier Science Inc., 2002.

Digital Library

[16]

L. Lulu and A. Elnagar, A comparative study between visibility-based roadmap path planning algorithms, Proc. IEEE/RSJ Intl. Conf. Intell. Robots Sys., 2005, pp. 3263--3268.

[17]

M. S. Marzouqi and R. A. Jarvis, New visibility-based path-planning approach for covert robotic navigation, Robotica, 24 (2006), 759--773.

Digital Library

[18]

J. S. B. Mitchell, Approximating watchman routes, Proc. 24th ACM-SIAM Sympos. Discrete Algo., 2013, pp. 844--855.

[19]

J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987.

Digital Library

[20]

M. Rao, G. Dudek, and S. Whitesides, Minimum distance localization for a robot with limited visibility, Proc. IEEE Intl. Conf. Robotics Automat., 2005, pp. 2438--2445.

[21]

H. Samet, Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, 2005.

Digital Library

[22]

S. Shekhar and S. Chawla, Spatial Databases: A Tour, Prentice Hall, 2003.

[23]

T. Siméon, J.-P. Laumond, and C. Nissoux, Visibility-based probabilistic roadmaps for motion planning, Advanced Robotics, 14 (2000), 477--493.

[24]

K. R. Varadarajan and P. K. Agarwal, Approximating shortest paths on a nonconvex polyhedron, SIAM J. Comput., 30 (2000), 1321--1340.

Digital Library

[25]

Wikipedia. Art gallery problem --- wikipedia, the free encyclopedia, 2013. {Online; accessed 1-July-2013}.

[26]

C. Zheng, H. Yin, J. Li, and M. Lu, A particle swarm optimization algorithm for least visual path problem in raster terrain, Proc. Intl. Conf. Intell. Comput. Bio-Medical Instr., 2011, 228--231.

Digital Library

Cited By

Agarwal PFox KSalzman O(2018)An Efficient Algorithm for Computing High-Quality Paths amid Polygonal ObstaclesACM Transactions on Algorithms10.1145/323065014:4(1-21)Online publication date: 21-Aug-2018
https://dl.acm.org/doi/10.1145/3230650
Savkin AHuang H(2017)Optimal Aircraft Planar Navigation in Static Threat EnvironmentsIEEE Transactions on Aerospace and Electronic Systems10.1109/TAES.2017.269660353:5(2413-2426)Online publication date: Oct-2017
https://doi.org/10.1109/TAES.2017.2696603
Agarwal PFox KSalzman O(2016)An efficient algorithm for computing high-quality paths amid polygonal obstaclesProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884517(1179-1192)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884517
Show More Cited By

Index Terms

Computing highly occluded paths on a terrain

Recommendations

Computing highly occluded paths using a sparse network
SIGSPATIAL '14: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Computing paths over a terrain that are highly occluded with respect to observers is an important problem in GIS. Given a fast algorithm for computing the visibility map, the path-planning step becomes the bottleneck. In this paper, we present an ...
Slope preserving lossy terrain compression

Accurate terrain representation with appropriate preservation of important terrain characteristics, especially slope steepness, is becoming more crucial and fundamental as the geographical models are becoming more complex. Based on our earlier success ...
Terrain Synthesis Based on Microscopic Terrain Feature
Edutainment '08: Proceedings of the 3rd international conference on Technologies for E-Learning and Digital Entertainment

In this paper, we use real terrain elevation data and the microscopic terrain feature unit to synthesize the macroscopic terrain flexibly and effectively. An interactive system provides users a convenient and intuitive interface to profile microscopic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL'13: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2013

598 pages

ISBN:9781450325219

DOI:10.1145/2525314

General Chairs:
Craig Knoblock
University of Southern California
,
Markus Schneider
University of Florida
,
Program Chairs:
Peer Kröger
Ludwig-Maximilians-Universität München, Germany
,
John Krumm
Microsoft Research
,
Peter Widmayer
ETH Zürich, Switzerland

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SIGSPATIAL'13

Sponsor:

SIGSPATIAL

SIGSPATIAL'13: 21st SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 5 - 8, 2013

Florida, Orlando

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
230
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Agarwal PFox KSalzman O(2018)An Efficient Algorithm for Computing High-Quality Paths amid Polygonal ObstaclesACM Transactions on Algorithms10.1145/323065014:4(1-21)Online publication date: 21-Aug-2018
https://dl.acm.org/doi/10.1145/3230650
Savkin AHuang H(2017)Optimal Aircraft Planar Navigation in Static Threat EnvironmentsIEEE Transactions on Aerospace and Electronic Systems10.1109/TAES.2017.269660353:5(2413-2426)Online publication date: Oct-2017
https://doi.org/10.1109/TAES.2017.2696603
Agarwal PFox KSalzman O(2016)An efficient algorithm for computing high-quality paths amid polygonal obstaclesProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884517(1179-1192)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884517
Agarwal PBeutel AMølhave T(2016)TerraNNIACM Transactions on Spatial Algorithms and Systems10.1145/27867572:2(1-31)Online publication date: 21-Jun-2016
https://dl.acm.org/doi/10.1145/2786757
Li WFranklin WBenedetti DMagalhães SHuang YSchneider MGertz MKrumm JSankaranarayanan J(2014)Parallel multiple observer siting on terrainProceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2666310.2666486(489-492)Online publication date: 4-Nov-2014
https://dl.acm.org/doi/10.1145/2666310.2666486
Lebeck NMølhave TAgarwal PHuang YSchneider MGertz MKrumm JSankaranarayanan J(2014)Computing highly occluded paths using a sparse networkProceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2666310.2666394(3-12)Online publication date: 4-Nov-2014
https://dl.acm.org/doi/10.1145/2666310.2666394

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents