کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414330 680890 2008 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A unified and efficient solution to the room search problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A unified and efficient solution to the room search problem
چکیده انگلیسی

We study the problem of searching for a mobile intruder in a polygonal region P with a door d (called a room) by a mobile searcher. The objective is to decide whether there exists a search schedule for the searcher to detect the intruder without allowing him to exit P through d, no matter how fast he moves, and if so, generate a search schedule. A searcher is called the k-searcher if he holds k flashlights and can see only along the rays of the flashlights emanating from his position, or two guards if two endpoints of the 1-searcher's flashlight move on the polygon boundary continuously.In this paper, we develop a simple, unified solution to the room search problem. The characterizations of the k-searchable and two-guard walkable rooms are all given in terms of components and deadlocks. A study on the structure of non-redundant components and deadlocks gives critical visibility events which occur in any search schedule, and a vertex of P at which our search schedule ends. Our characterizations are not only simple but also lead to efficient algorithms for all decision problems and schedule reporting problems. Particularly, we present optimal O(n) time algorithms for determining the 1-searchability and the two-guard walkability of a room, and an O(nlogn+m) time and O(n) space algorithm for generating a search schedule, if it exists, where n is the number of vertices of P and m(⩽n2) is the number of search instructions reported.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 40, Issue 1, May 2008, Pages 45-60