【摘 要】
:
This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually "see" an intruder that is unpredictable and capable of
【机 构】
:
School of High-Technology for Human Welfare
【基金项目】
:
Some preliminary results of this paper were presented at
论文部分内容阅读
This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually "see" an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time.We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the searchers having only one flashlight and the one of the searchers having full 360° vision is simply established, and moreover, an optimal O(n) time and space algorithm for determining the searchability of simple polygons is obtained. We also give an O(n log n + I) time algorithm for generating a search schedule if it exists, where I (< 3n2) is the number of search instructions reported. Our results improve upon the previously known O(n2) time and space bounds.
其他文献
Due to large topography slopes in natural rivers, pollutant concentration embodies a property of three-dimensional distribution when wastewater is discharged fr
The title compound, 2,6-bis(benzimidazo(1,2-c)quinazolin-6-yl)pyridine tetrahy-drate, was synthesized by simple condensation of 2-(2-sminophenyl) benzimidazole
We compared four esterifiable enzymes. The lipase Novozym 435 possessed the highest activity for the conjugated linoleic acid esterification during the synthesi
helpful tool to evaluate the retention characteristics of ionic liquid systems and to understand the interactions of solutes and ionic liquids.
A multiple-elastic beam model based on Euler-Bernoulli-beam theory is presented to investigate the nonlinear dynamic instability of double-walled nanotubes.Taki
Warm compaction and room temperature compaction were applied to prepare bonded Nd-Fe-B magnets. The results indicated that the density of magnet was determined
Carbon materials were prepared using mesoporous silica HMS with different pore sizes as the hard templates and water-soluble phenolic resin as the carbon source
The settling and hydrodynamic properties of 3-D fractal flocs in quiescent water are investigated with a numerical model based on the Lattice Boltzmann Method (
Thermosetting acrylic coatings were prepared by using carboxyl acid group-containing acrylic oligomer and curing with titanium-oxo-clusters which were first pre
Ammonium metavanadate(10 mol%) was found to be a useful catalyst for the synthesis of various 2-substituted aryl benzimidazoles.It was used as an oxidizing agen