PIECEWISE-LINEAR PATHS AMONG CONVEX OBSTACLES

Let B be a set of n arbitrary (possibly intersecting) convex obstacles in R(d). It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting of O(n((d-1)[d/2+1])) segments. The bound cannot be improved below Omega(n(d)); thus, in R(3), the answer is between n(3) and n(4). For open disjoint convex obstacles, a Theta(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case.
Publisher
SPRINGER VERLAG
Issue Date
1995-07
Language
ENG
Citation

DISCRETE COMPUTATIONAL GEOMETRY, v.14, no.1, pp.9 - 29

ISSN
0179-5376
URI
http://hdl.handle.net/10203/73592
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 124
  • Download : 0
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 5 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0