Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Computing thek-Visibility Region of a Point in a Polygon

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

Two pointsp andq in a simple polygonP arek-visible when the line segmentpq crosses the boundary ofP at mostk times. Given a query pointq, a positive integerk, and a polygonP, we design an algorithm that computes the region ofP that isk-visible fromq inO(nk) time, wheren denotes the number of vertices ofP. This region is called thek-visibility region ofq. This is the first algorithm parameterized in terms ofk, resulting in an asymptotically faster worst-case running time compared to previous algorithms whenk is\(o(\log {n})\), and bridging the gap between theO(n)-time algorithm for computing the 0-visibility region ofq inP and the\(O(n\log n)\)-time algorithm for computing thek-visibility region ofq inP for anyk.

We also design a data structure of sizeO(n5) that supports visibility queries, returning thek-visible region ofP for any arbitrary query pointq in\(O(\log {n}+m)\) time, wherem denotes the number of vertices on the boundary of the output visibility region.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Notes

  1. All indices are computed modulo the size of the corresponding vertex set:m + 1 in this case.

References

  1. Aichholzer, O., Fabila-Monroy, R., Flores-Peñaloza, D., Hackl, T., Huemer, C., Urrutia, J., Vogtenhuber, B.: Modem illumination of monotone polygons. Comput. Geom.68, 101–118 (2018)

    MathSciNet MATH  Google Scholar 

  2. Alt, H., Godau, M.: Computing the fréchet distance between two polygonal curves. Int. J. Comput. Geom. Appl.5(01n02), 75–91 (1995)

    MATH  Google Scholar 

  3. Aronov, B., Guibas, L. J., Teichmann, M., Zhang, L.: Visibility queries and maintenance in simple polygons. Discrete Comput. Geom.27(4), 461–483 (2002)

    MathSciNet MATH  Google Scholar 

  4. Bahoo, Y., Banyassady, B., Bose, P., Durocher, S., Mulzer, W.: A time-space trade-off for computing the k-visibility region of a point in a polygon. Theor. Comput. Sci. (2018)

  5. Bajuelos, A., Canales, S., Hernández, G., Martins, M.: A hybrid metaheuristic strategy for covering with wireless devices. J. Univers. Comput. Sci.18(14), 1906–1932 (2012)

    MathSciNet MATH  Google Scholar 

  6. Ballinger, B., Benbernou, N., Bose, P., Damian, M., Demaine, E., Dujmović, V., Flatland, R., Hurtado, F., Iacono, J., Lubiw, A., et al.: Coverage with k-transmitters in the presence of obstacles. J. Comb. Optim.25(2), 208–233 (2013)

    MathSciNet MATH  Google Scholar 

  7. Birchfield, S.: An introduction to projective geometry (for computer vision). Unpublished note, Stanford university (1998)

  8. Bose, P., Lubiw, A., Munro, J.: Efficient visibility queries in simple polygons. Comput. Geom.23(3), 313–335 (2002)

    MathSciNet MATH  Google Scholar 

  9. Brink, W.: Lecture notes in computer vision, Fall (2017)

  10. Cannon, S., Fai, T., Iwerks, J., Leopold, U., Schmidt, C.: Combinatorics and complexity of guarding polygons with edge and point 2-transmitters. arXiv:1503.05681 (2015)

  11. Chang, H. C., Erickson, J., Xu, C.: Detecting weakly simple polygons. In: Proceeding 26th ACM-SIAM Symposium on Discrete Algorithms (SODA, pp 1655–1670 (2014)

  12. Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom.6(3), 485–524 (1991)

    MathSciNet MATH  Google Scholar 

  13. Davis, L., Benedikt, M.: Computational models of space: isovists and isovist fields citeseer (1979)

  14. De Berg, M., Cheong, O., Van Kreveld, M., Overmars, M.: Computational Geometry: Introduction. Springer, Berlin (2008)

    MATH  Google Scholar 

  15. Dean, J., Lingas, A., Sack, J.: Recognizing polygons, or how to spy. Vis. Comput.3(6), 344–355 (1988)

    MATH  Google Scholar 

  16. Duque, F., Hidalgo-Toscano, C.: An upper bound on the k-modem illumination problem. arXiv:1410.4099 (2014)

  17. El Gindy, H., Avis, D.: A linear algorithm for computing the visibility polygon from a point. J. Algorithms2(2), 186–197 (1981)

    MathSciNet MATH  Google Scholar 

  18. Hoffmann, K., Mehlhorn, K., Rosenstiehl, P., Tarjan, R.: Sorting Jordan sequences in linear time using level-linked search trees. Inf. Control.68 (1-3), 170–184 (1986)

    MathSciNet MATH  Google Scholar 

  19. Huang, H., Ni, C., Ban, X., Gao, J., Schneider, A., Lin, S.: Connected wireless camera network deployment with visibility coverage. In: INFOCOM Proceedings IEEE, pp 1204–1212. IEEE (2014)

  20. Joe, B., Simpson, R.: Corrections to lee’s visibility polygon algorithm. BIT Numer. Math.27(4), 458–473 (1987)

    MATH  Google Scholar 

  21. Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM J. Comput.12(1), 28–35 (1983)

    MathSciNet MATH  Google Scholar 

  22. Lee, D.: Visibility of a simple polygon. Comput. Vis. Graph. Image Process.22(2), 207–221 (1983)

    MATH  Google Scholar 

  23. Meguerdichian, S., Koushanfar, F., Qu, G., Potkonjak, M.: Exposure in wireless ad-hoc sensor networks. In: Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, pp 139–150. ACM (2001)

  24. Mouawad, N., Shermer, T.: The superman problem. Vis. Comput.10(8), 459–473 (1994)

    Google Scholar 

  25. Murray, A., Kim, K., Davis, J., Machiraju, R., Parent, R.: Coverage optimization to support security monitoring. Comput. Environ. Urban Syst.31(2), 133–147 (2007)

    Google Scholar 

  26. o’Rourke, J., et al.: Computational geometry in C. Cambridge University Press, Cambridge (1998)

    MATH  Google Scholar 

  27. Rosenstiehl, P.: Planar permutations defined by two intersecting Jordan curves. Graph Theory Combin., 259–271 (1984)

  28. Wang, Y., Hu, C., Tseng, Y.: Efficient deployment algorithms for ensuring coverage and connectivity of wireless sensor networks. In: Wireless Internet, 2005. Proceedings First International Conference on, pp 114–121. IEEE (2005)

Download references

Author information

Authors and Affiliations

  1. University of Windsor and CAMufacturing Solutions, Windsor, Canada

    Yeganeh Bahoo

  2. Carleton University, Ottawa, Canada

    Prosenjit Bose

  3. University of Manitoba, Winnipeg, Canada

    Stephane Durocher

  4. Inria, CNRS, Grenoble Institute of Engineering, LJK, Université Grenoble Alpes, Grenoble, France

    Stephane Durocher

  5. Simon Fraser University, Vancouver, Canada

    Thomas C. Shermer

Authors
  1. Yeganeh Bahoo

    You can also search for this author inPubMed Google Scholar

  2. Prosenjit Bose

    You can also search for this author inPubMed Google Scholar

  3. Stephane Durocher

    You can also search for this author inPubMed Google Scholar

  4. Thomas C. Shermer

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toYeganeh Bahoo.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article belongs to the Topical Collection:Special Issue on International Workshop on Combinatorial Algorithms (IWOCA 2019)

Guest Editors: Charles Colbourn, Roberto Grossi, Nadia Pisanti

Rights and permissions

About this article

Associated Content

Part of a collection:

International Workshop on Combinatorial Algorithms (IWOCA 2019)

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp