A NEAR-QUADRATIC ALGORITHM FOR PLANNING THE MOTION OF A POLYGON IN A POLYGONAL ENVIRONMENT

Authors
HALPERIN D SHARIR M
Citation
D. Halperin et M. Sharir, A NEAR-QUADRATIC ALGORITHM FOR PLANNING THE MOTION OF A POLYGON IN A POLYGONAL ENVIRONMENT, Discrete & computational geometry, 16(2), 1996, pp. 121-134
Citations number
17
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
16
Issue
2
Year of publication
1996
Pages
121 - 134
Database
ISI
SICI code
0179-5376(1996)16:2<121:ANAFPT>2.0.ZU;2-X
Abstract
We consider the problem of planning the motion of an arbitrary k-sided polygonal robot B, free to translate and rotate in a polygonal enviro nment V bounded by n edges. We present an algorithm that constructs a single component of the free configuration space of B in time O((kn)(2 +epsilon)), for any epsilon > 0. This algorithm, combined with some st andard techniques in motion planning, yields a solution to the underly ing motion-planning problem, within the same running time.