EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2152. Online Exploration of Rectilinear Polygons by Multiple Searchers
Invited abstract in session WD-25: Topics in Combinatorial Optimization II (Contributed), stream Combinatorial Optimization.
Wednesday, 14:30-16:00Room: 011 (building: 208)
Authors (first author is the speaker)
| 1. | Taro Abe
|
| University of Hyogo | |
| 2. | Yuya Higashikawa
|
| University of Hyogo | |
| 3. | Shuichi Miyazaki
|
| Graduate School of Information Science, University of Hyogo |
Abstract
We consider a problem faced by multiple searchers that have to explore an unknown simple polygon P. At the beginning of the exploration, all the searcher are located at some point inside P, called the origin, and the exploration finishes when any point on the boundary of P is seen by at least one searcher and all the searchers return to the origin. The cost of the exploration is the time needed to finish the exploration, and the objective of the problem is to minimize it. We consider an online exploration, where the searchers create a map of P during the exploration and use it to decide which direction to move.
In this paper, we consider a restricted class of simple rectilinear polygons, which can be created by, starting from the root rectangle, recursively attaching a base of a new rectangle to a lateral side of some rectangle constituting the current object. We present an online exploration algorithm for this class of polygons, and show an upper bound on its competitive ratio that is sublinear in the number of searchers.
Keywords
- Algorithms
- Computer Science/Applications
- Combinatorial Optimization
Status: accepted
Back to the list of papers