Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons | SpringerLink
Skip to main content
Springer Nature Link
Log in

Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons

  • Conference paper
  • First Online:
LATIN 2016: Theoretical Informatics (LATIN 2016)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9644))

Included in the following conference series:

Abstract

We establish tight bounds for beacon-based coverage problems. In particular, we show that \(\lfloor \frac{n}{6} \rfloor \) beacons are always sufficient and sometimes necessary to cover a simple rectilinear polygon P with n vertices. When P is monotone and rectilinear, we prove that this bound becomes \(\lfloor \frac{n+4}{8} \rfloor \). We also present an optimal linear-time algorithm for computing the beacon kernel of P.

Work by S.W.Bae was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (2013R1A1A1A05006927) and by the Ministry of Education (2015R1D1A1A01057220). Work by C.-S. Shin was supported by Research Grant of Hankuk University of Foreign Studies. Work by A. Vigneron was supported by KAUST base funding.

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

Access this chapter

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

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    A chord c of a polygon is a line segment between two points on the boundary such that all points on c except the two endpoints lie in the interior of the polygon.

References

  1. Biro, M.: Beacon-based routing and guarding. Dissertation, Stony Brook University (2013)

    Google Scholar 

  2. Biro, M., Gao, J., Iwerks, J., Kostitsyna, I., Mitchell, J.S.B.: Combinatorics of beacon-based routing and coverage. In: Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG ) (2013)

    Google Scholar 

  3. Biro, M., Iwerks, J., Kostitsyna, I., Mitchell, J.S.B.: Beacon-based algorithms for geometric routing. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 158–169. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  4. Chavátal, V.: A combinatorial theorem in plane geometry. J. Combinat. Theory Series B 18, 39–41 (1975)

    Article  MathSciNet  Google Scholar 

  5. Györi, E.: A short proof of the rectilinear art gallery theorem. SIAM J. Algebraic Discrete Methods 7(3), 452–454 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  6. Györi, E., Hoffmann, F., Kriegel, K., Shermer, T.: Generalized guarding, partitioning for rectilinear polygons. Comput. Geom. Theory Appl. 6(1), 21–44 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  7. Kahn, J., Klawe, M., Kleitman, D.: Traditional galleries require fewer watchmen. SIAM J. Algebraic Discrete Methods 4(2), 194–206 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  8. Kouhestani, B., Rappaport, D., Salmoaa, K.: Routing in a polygonal terrain with the shortest beacon watchtower. In: Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG ) (2014)

    Google Scholar 

  9. Michael, T.S., Pinciu, V.: Art gallery theorems for guarded guards. Comput. Geom. Theory Appl. 26, 247–258 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  10. O’Rourke, J.: An alternative proof of the rectilinear art gallery theorem. J. Geom. 21, 118–130 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  11. O’Rourke, J.: Art Gallery Theorems and Algorithms. International Series of Monographs on Computer Sciences. Oxford University Press, New York (1987)

    MATH  Google Scholar 

  12. Shermer, T.: Recent results in art galleries. IEEE Proc. 90(9), 1384–1399 (1992)

    Article  Google Scholar 

  13. Shermer, T.C.: A combinatorial bound for beacon-based routing in orthogonal polygons. In: Proceedings of CCCG 2015, pp. 213–219 (2015)

    Google Scholar 

  14. Urrutia, J.: Art gallery and illumination problems (chap. 22). In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 973–1027. North-Holland (2000)

    Google Scholar 

Download references

Acknowledgments

We thank the anonymous referees for their helpful comments.

Author information

Authors and Affiliations

  1. Department of Computer Science, Kyonggi University, Suwon, Korea

    Sang Won Bae

  2. Division of Computer and Electronic Systems Engineering, Hankuk University of Foreign Studies, Yongin, Korea

    Chan-Su Shin

  3. Visual Computing Center, King Abdullah University of Science and Technology (KAUST), Thuwal, 23955-6900, Saudi Arabia

    Antoine Vigneron

Authors
  1. Sang Won Bae
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chan-Su Shin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Antoine Vigneron
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Antoine Vigneron .

Editor information

Editors and Affiliations

  1. Carleton University, Ottawa, ON, Ontario, Canada

    Evangelos Kranakis

  2. University Chile, Santiago, Chile

    Gonzalo Navarro

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bae, S.W., Shin, CS., Vigneron, A. (2016). Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons. In: Kranakis, E., Navarro, G., Chávez, E. (eds) LATIN 2016: Theoretical Informatics. LATIN 2016. Lecture Notes in Computer Science(), vol 9644. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49529-2_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-49529-2_9

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-662-49528-5

  • Online ISBN: 978-3-662-49529-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation