516:
573:
20:
145:
83:
in the general case, but there exist efficient approximation algorithms that run in polynomial time based on the idea of finding a suitable sample of points on the obstacle edges and performing a visibility graph calculation using these sample points.
91:, the problem is to compute a shortest path that never leaves the surface and connects s with t. This is a generalization of the problem from 2-dimension but it is much easier than the 3-dimensional problem.
103:, i.e., one can go through an obstacle, but it incurs an extra cost to go through an obstacle. The standard problem is the special case where the obstacles have infinite weight. This is termed as the
105:
325:
Kapoor, S.; Maheshwari, S. N.; Mitchell, Joseph S. B. (1997), "An efficient algorithm for
Euclidean shortest paths among polygonal obstacles in the plane",
59:
needed to perform such calculations. These algorithms are based on two different principles, either performing a shortest path algorithm such as
288:
Kapoor, S.; Maheshwari, S. N. (1988), "Efficient algorithms for
Euclidean shortest path and visibility problems with polygonal obstacles",
87:
There are many results on computing shortest paths which stays on a polyhedral surface. Given two points s and t, say on the surface of a
162:
Aleksandrov, Lyudmil; Maheshwari, Anil; Sack, Joerg (2005), "Determining approximate shortest paths in weighted polyhedral surfaces",
614:
557:
419:
55:
in a model of computation allowing addition and comparisons of real numbers, despite theoretical difficulties involving the
327:
289:
215:
307:
233:
204:
638:
633:
643:
56:
43:, and two points, find the shortest path between the points that does not intersect any of the obstacles.
607:
193:
Chiang, Yi-Jen; Mitchell, Joseph S. B. (1999), "Two-point
Euclidean shortest path queries in the plane",
355:
214:
Choi, Joonsoo; Sellen, Jürgen; Yap, Chee-Keng (1994), "Approximate
Euclidean shortest path in 3-space",
550:
257:
500:
271:
648:
588:
531:
124:
60:
600:
351:
266:
32:
19:
470:
118:
543:
434:
8:
374:
466:
454:
430:
313:
239:
181:
164:
194:
415:
303:
229:
200:
88:
458:
446:
407:
386:
336:
317:
295:
276:
221:
173:
64:
185:
403:
243:
71:
method) propagating a wavefront from one of the points until it meets the other.
52:
40:
584:
527:
411:
280:
627:
523:
377:(1984), "Euclidean shortest paths in the presence of rectilinear barriers",
177:
390:
370:
359:
252:
255:(1999), "An optimal algorithm for Euclidean shortest paths in the plane",
225:
299:
515:
450:
341:
36:
148:", Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49-60.
496:
580:
80:
23:
Example of a shortest path in a three-dimensional
Euclidean space
196:
Proc. 10th ACM-SIAM Symposium on
Discrete Algorithms (SODA 1999)
572:
435:"Computing the external geodesic diameter of a simple polygon"
356:"Approximating shortest paths on weighted polyhedral surfaces"
99:
There are variations of this problem, where the obstacles are
16:
Problem of computing shortest paths around geometric obstacles
146:
New lower bound techniques for robot motion planning problems
400:
Euclidean
Shortest Paths: Exact or Approximate Algorithms
199:, Association for Computing Machinery, pp. 215–224,
161:
67:
derived from the obstacles or (in an approach called the
324:
471:"Computing geodesic properties inside a simple polygon"
349:
217:Proc. 10th ACM Symposium on Computational Geometry
291:Proc. 4th ACM Symposium on Computational Geometry
625:
287:
79:In three (and higher) dimensions the problem is
51:In two dimensions, the problem can be solved in
428:
250:
192:
608:
551:
213:
369:
615:
601:
558:
544:
465:
340:
270:
499:of Euclidean Shortest Path algorithm in
397:
18:
626:
328:Discrete & Computational Geometry
567:
510:
398:Li, Fajie; Klette, Reinhard (2011),
74:
13:
350:Lanthier, Mark; Maheshwari, Anil;
121:, in a graph of edges and vertices
14:
660:
490:
478:Revue d'Intelligence Artificielle
46:
571:
514:
138:
1:
155:
587:. You can help Knowledge by
530:. You can help Knowledge by
7:
112:
94:
10:
665:
566:
509:
144:J. Canny and J. H. Reif, "
412:10.1007/978-1-4471-2256-2
281:10.1137/S0097539795289604
258:SIAM Journal on Computing
501:Digital Geometric Kernel
131:
31:problem is a problem in
178:10.1145/1044731.1044733
125:Any-angle path planning
106:weighted region problem
29:Euclidean shortest path
639:Computational geometry
526:-related article is a
467:Toussaint, Godfried T.
431:Toussaint, Godfried T.
391:10.1002/net.3230140304
33:computational geometry
24:
226:10.1145/177424.177501
119:Shortest path problem
22:
634:Geometric algorithms
294:, pp. 172–182,
61:Dijkstra's algorithm
644:Combinatorics stubs
300:10.1145/73393.73411
251:Hershberger, John;
109:in the literature.
69:continuous Dijkstra
57:numerical precision
451:10.1007/BF02247961
364:, pp. 527–562
352:Sack, Jörg-Rüdiger
342:10.1007/PL00009323
220:, pp. 41–48,
165:Journal of the ACM
25:
596:
595:
539:
538:
421:978-1-4471-2255-5
127:, in a grid space
89:convex polyhedron
75:Higher dimensions
35:: given a set of
656:
617:
610:
603:
581:geometry-related
575:
568:
560:
553:
546:
518:
511:
485:
475:
461:
424:
393:
375:Preparata, F. P.
365:
345:
344:
320:
283:
274:
265:(6): 2215–2256,
246:
209:
188:
149:
142:
65:visibility graph
664:
663:
659:
658:
657:
655:
654:
653:
624:
623:
622:
621:
565:
564:
507:
493:
473:
429:Samuel, David;
422:
404:Springer-Verlag
310:
236:
207:
158:
153:
152:
143:
139:
134:
115:
97:
77:
53:polynomial time
49:
41:Euclidean space
39:obstacles in a
17:
12:
11:
5:
662:
652:
651:
649:Geometry stubs
646:
641:
636:
620:
619:
612:
605:
597:
594:
593:
576:
563:
562:
555:
548:
540:
537:
536:
519:
505:
504:
497:Implementation
492:
491:External links
489:
488:
487:
463:
426:
420:
395:
385:(3): 393–410,
367:
347:
335:(4): 377–383,
322:
308:
285:
272:10.1.1.47.2037
248:
234:
211:
205:
190:
157:
154:
151:
150:
136:
135:
133:
130:
129:
128:
122:
114:
111:
96:
93:
76:
73:
48:
47:Two dimensions
45:
15:
9:
6:
4:
3:
2:
661:
650:
647:
645:
642:
640:
637:
635:
632:
631:
629:
618:
613:
611:
606:
604:
599:
598:
592:
590:
586:
583:article is a
582:
577:
574:
570:
569:
561:
556:
554:
549:
547:
542:
541:
535:
533:
529:
525:
524:combinatorics
520:
517:
513:
512:
508:
502:
498:
495:
494:
483:
479:
472:
468:
464:
460:
456:
452:
448:
444:
440:
436:
432:
427:
423:
417:
413:
409:
405:
401:
396:
392:
388:
384:
380:
376:
372:
368:
363:
362:
357:
353:
348:
343:
338:
334:
330:
329:
323:
319:
315:
311:
309:0-89791-270-5
305:
301:
297:
293:
292:
286:
282:
278:
273:
268:
264:
260:
259:
254:
253:Suri, Subhash
249:
245:
241:
237:
235:0-89791-648-4
231:
227:
223:
219:
218:
212:
208:
206:9780898714340
202:
198:
197:
191:
187:
183:
179:
175:
171:
167:
166:
160:
159:
147:
141:
137:
126:
123:
120:
117:
116:
110:
108:
107:
102:
92:
90:
85:
82:
72:
70:
66:
62:
58:
54:
44:
42:
38:
34:
30:
21:
589:expanding it
578:
532:expanding it
521:
506:
481:
477:
442:
438:
399:
382:
378:
361:Algorithmica
360:
332:
326:
290:
262:
256:
216:
195:
169:
163:
140:
104:
100:
98:
86:
78:
68:
50:
28:
26:
445:(1): 1–19,
628:Categories
371:Lee, D. T.
156:References
37:polyhedral
484:(2): 9–42
439:Computing
267:CiteSeerX
172:: 25–53,
503:software
469:(1989),
459:31450333
433:(1990),
379:Networks
354:(2001),
113:See also
101:weighted
95:Variants
318:9599057
81:NP-hard
457:
418:
316:
306:
269:
242:
232:
203:
186:697658
184:
579:This
522:This
474:(PDF)
455:S2CID
314:S2CID
244:69747
240:S2CID
182:S2CID
132:Notes
63:on a
585:stub
528:stub
416:ISBN
304:ISBN
230:ISBN
201:ISBN
27:The
447:doi
408:doi
387:doi
337:doi
296:doi
277:doi
222:doi
174:doi
630::
480:,
476:,
453:,
443:44
441:,
437:,
414:,
406:,
402:,
383:14
381:,
373:;
358:,
333:18
331:,
312:,
302:,
275:,
263:28
261:,
238:,
228:,
180:,
170:52
168:,
616:e
609:t
602:v
591:.
559:e
552:t
545:v
534:.
486:.
482:3
462:.
449::
425:.
410::
394:.
389::
366:.
346:.
339::
321:.
298::
284:.
279::
247:.
224::
210:.
189:.
176::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
