The search functionality is under construction.
The search functionality is under construction.

Author Search Result

[Author] Luan LIU(1hit)

1-1hit
  • Exploring the Outer Boundary of a Simple Polygon

    Qi WEI  Xiaolin YAO  Luan LIU  Yan ZHANG  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2021/04/02
      Vol:
    E104-D No:7
      Page(s):
    923-930

    We investigate an online problem of a robot exploring the outer boundary of an unknown simple polygon P. The robot starts from a specified vertex s and walks an exploration tour outside P. It has to see all points of the polygon's outer boundary and to return to the start. We provide lower and upper bounds on the ratio of the distance traveled by the robot in comparison to the length of the shortest path. We consider P in two scenarios: convex polygon and concave polygon. For the first scenario, we prove a lower bound of 5 and propose a 23.78-competitive strategy. For the second scenario, we prove a lower bound of 5.03 and propose a 26.5-competitive strategy.