Searching a Circular Corridor with Two Flashlights | SpringerLink
Skip to main content
Springer Nature Link
Log in

Searching a Circular Corridor with Two Flashlights

  • Conference paper
Theory and Applications of Models of Computation (TAMC 2009)

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

  • 597 Accesses

Abstract

We consider the problem of searching for a mobile intruder in a circular corridor (a polygon with one polygonal hole) by two searchers, who hold a flashlight. Both searchers move on the outer boundary, directing their flashlights at the inner boundary. The objective is to decide whether there exists a search schedule for the searchers to detect the intruder, no matter how fast he moves. We give a characterization of the class of circular corridors, which are searchable with two flashlights. Based on our characterization, an O(n logn) time algorithm is then presented to determine the searchability of a circular corridor with two flashlights, where n denotes the total number of vertices of the outer and inner boundaries. Moreover, a search schedule can be output in time linear in its size, if it exists. Our result gives the first efficient solution to the polygon search problem for two searchers.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Chazelle, B., Guibas, L.: Visibility and intersection problem in plane geometry. Discrete Comput. Geom. 4, 551–581 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  2. Guibas, L.J., Latombe, J.C., Lavalle, S.M., Lin, D., Motwani, R.: Visibility-based pursuit-evasion in a polygonal environment. Int. J. Comput. Geom. & Appl. 9, 471–493 (1999)

    Article  MathSciNet  Google Scholar 

  3. Heffernan, P.J.: An optimal algorithm for the two-guard problem. IJCGA 6, 15–44 (1996)

    MATH  MathSciNet  Google Scholar 

  4. Icking, C., Klein, R.: The two guards problem. IJCGA 2, 257–285 (1992)

    MATH  MathSciNet  Google Scholar 

  5. Kameda, T., Zhang, J.Z., Yamashita, M.: Searching a circular corridor by two boundary 1-searchers. In: Proc. KyotoCGGT 2007 (2007)

    Google Scholar 

  6. LaValle, S.M., Simov, B., Slutzki, G.: An algorithm for searching a polygonal region with a flashlight. IJCGA 12, 87–113 (2002)

    MATH  MathSciNet  Google Scholar 

  7. Lee, J.H., Park, S.M., Chwa, K.Y.: Searching a polygonal room with one door by a 1-searcher. IJCGA 10, 201–220 (2000)

    MATH  MathSciNet  Google Scholar 

  8. Simov, B.H., LaVallel, S.M., Slutzki, G.: A complete pursuit-evasion algorithm for two pursuers using beam dectection. In: Proc. IEEE Int’l. Conf. Robotics Automation, pp. 618–623 (2002)

    Google Scholar 

  9. Suzuki, I., Yamashita, M.: Searching for mobile intruders in a polygonal region. SIAM J. Comp. 21, 863–888 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  10. Tan, X.: A unified and efficient solution to the room search problem. Comput. Geom. Theory Appl. 40, 45–60 (2008)

    MATH  Google Scholar 

  11. Tan, X.: Searching a polygonal region by a boundary searcher. J. Comput. Sci. Tech. (to appear)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Inform. Sci. and Tech., Dalian Martime University, China

    Bo Jiang & Xuehou Tan

  2. Tokai University, 317 Nishino, Numazu, 410-0395, Japan

    Xuehou Tan

Authors
  1. Bo Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xuehou Tan
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science and Engineering, Texas A&M University, College Station, 77843, Texas, USA

    Jianer Chen

  2. School of Mathematics, University of Leeds, LS2 9JT, U.K.

    S. Barry Cooper

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Jiang, B., Tan, X. (2009). Searching a Circular Corridor with Two Flashlights. In: Chen, J., Cooper, S.B. (eds) Theory and Applications of Models of Computation. TAMC 2009. Lecture Notes in Computer Science, vol 5532. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02017-9_37

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02017-9_37

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02016-2

  • Online ISBN: 978-3-642-02017-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation