home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / fnet / seminair / 97 < prev    next >
Encoding:
Internet Message Format  |  1993-01-24  |  1.3 KB
  1. Path: sparky!uunet!utcsri!skule.ecf!torn!spool.mu.edu!cass.ma02.bull.com!mips2!bull.bull.fr!julienas!seti!sophia.inria.fr
  2. From: Monique.Teillaud@sophia.inria.fr (Monique Teillaud-Devillers)
  3. Newsgroups: fnet.seminaires
  4. Subject: seminaire Prisme
  5. Message-ID: <4878@seti.inria.fr>
  6. Date: 21 Jan 93 09:57:30 GMT
  7. Sender: news@seti.inria.fr
  8. Distribution: fnet
  9. Lines: 26
  10. Approved: werner@margaux.inria.fr
  11. Jour: 28/01/93
  12. Lieu: INRIA Sophia-Antipolis
  13.  
  14.  
  15.  
  16.  
  17. Jeudi 28 janvier
  18. 10h
  19.  
  20. INRIA Sophia-Antipolis
  21. salle B118
  22.  
  23. Otfried Schwarzkopf (Universite d'Utrecht)
  24. Piecewise Linear Paths Among Convex Obstacles
  25.  
  26.  
  27. Let B be a set of $n$ arbitrary (possibly intersecting) convex
  28. obstacles in $R^d$. It is shown that any two points which can be
  29. connected by a path avoiding the obstacles can also be connected by a
  30. path consisting of $O(n^{(d-1)\lfloor{d/2+1}\rfloor})$ segments. The
  31. bound cannot be improved below $\Omega(n^d)$; thus in $R^3$, the
  32. answer is between $n^3$ and $n^4$.  For disjoint obstacles, a
  33. $\Theta(n)$ bound is proved.  By a well-known reduction, the general
  34. case result also upper bounds the complexity for a translational
  35. motion of an arbitrary convex robot among convex obstacles.
  36. In the planar case, asymptotically tight bounds and efficient
  37. algorithms are given.
  38.  
  39. (travail effectue en collaboration avec Mark de Berg et Jiri Matousek)
  40.