DocumentCode :
3106313
Title :
Pursuit-Evasion Voronoi Diagrams in ell_1
Author :
Cheung, Warren ; Evans, William
Author_Institution :
Univ. of British Columbia, Vancouver
fYear :
2007
fDate :
9-11 July 2007
Firstpage :
58
Lastpage :
65
Abstract :
We are given m pursuers and one evader. Each pursuer and the evader has an associated starting point in the plane, a maximum speed, and a start time. We also have a set of line segment obstacles with a total of n endpoints. Our task is to find those points in the plane, called the evader´s region, that the evader can reach via evasive paths. A path is evasive if the evader can traverse the path from its starting point without encountering a pursuer along the way. The evader and the pursuers must obey their start time and speed constraints, and cannot go through obstacles. The partition of the plane into the evader´s region and the remaining pursuers´ region is called the pursuit-evasion Voronoi diagram. We study pursuit-evasion Voronoi diagrams for the lscr1 metric. We show that the complexity of the diagram is O((n + m)2(mn + m)) and that it can be calculated in polynomial time.
Keywords :
computational complexity; computational geometry; polynomials; polynomial time; pursuit-evasion Voronoi diagrams; Additives; Bioinformatics; Computer science; Councils; Polynomials; Tellurium; Time factors; Turning;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Voronoi Diagrams in Science and Engineering, 2007. ISVD '07. 4th International Symposium on
Conference_Location :
Glamorgan
Print_ISBN :
0-7695-2869-4
Type :
conf
DOI :
10.1109/ISVD.2007.33
Filename :
4276105
Link To Document :
بازگشت