Skip to main content
Log in

Coverage problems and visibility regions on topographic surfaces

  • Section III Covering
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The viewshed of a point on an irregular topographic surface is defined as the area visible from the point. The area visible from a set of points is the union of their viewsheds. We consider the problems of locating the minimum number of viewpoints to see the entire surface, and of locating a fixed number of viewpoints to maximize the area visible, and possible extensions. We discuss alternative methods of representing the surface in digital form, and adopt a TIN or triangulated irregular network as the most suitable data structure. The space is tesselated into a network of irregular triangles whose vertices have known elevations and whose edges join vertices which are Thiessen neighbours, and the surface is represented in each one by a plane. Visibility is approximated as a property of each triangle: a triangle is defined as visible from a point if all of its edges are fully visible. We present algorithms for determination of visibility, and thus reduce the problems to variants of the location set covering and maximal set covering problems. We examine the performance of a variety of heuristics.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. K.E. Brassel and D. Reif, A procedure to generate Thiessen polygons, Geographical Analysis 11 (1979) 289.

    Google Scholar 

  2. P.A. Burrough,Principles of Geographic Information Systems for Land Resources Assessment (Oxford University Press, 1986).

  3. R.L. Church and C.S. Revelle, The maximal covering location problem, Papers, Regional Science Association 32 (1974) 101.

    Google Scholar 

  4. L. de Floriani, B. Falcidieno and C. Pienovi, Delaunay-based representation of surfaces defined over arbitrarily shaped domains, Computer Graphics, Vision and Image Processing 32 (1985) 127.

    Google Scholar 

  5. L. de Floriani, B. Falcidieno, C. Pienovi, D. Allen and G. Nagy, A visibility-based model for terrain features,Proceedings, Second International Symposium on Spatial Data Handling, Seattle (1986) 235.

  6. D.T. Lee and B.J. Schachter, Two algorithms for constructing a Delaunay triangulation, International Journal of Computer and Information Sciences 9 (1980) 219.

    Article  Google Scholar 

  7. B.B. Mandelbrot,The Fractal Geometry of Nature (Freeman, San Francisco, 1982).

    Google Scholar 

  8. D.M. Mark, Recursive algorithm for determination of proximal (Thiessen) polygons in any metric space, Geographical Analysis 19 (1987) 264.

    Google Scholar 

  9. T.K. Peucker, R.J. Fowler, J.J. Little and D.M. Mark, The triangulated irregular network, Proceedings, Digital Terrain Models Symposium, ASP/ACSM (1978) 516.

  10. C. ReVelle, Personal communication, 1987

  11. A. Tarvydas, Terrain approximation by triangular facets, Paper prepared for AutoCarto 6, Ottawa, 1983.

  12. C. Toregas and C. ReVelle, Optimum location under time and distance constraints, Papers and Proceedings, Regional Science Association 28 (1972) 133.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Goodchild, M.F., Lee, J. Coverage problems and visibility regions on topographic surfaces. Ann Oper Res 18, 175–186 (1989). https://doi.org/10.1007/BF02097802

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02097802

Keywords

Navigation