Sariel Har-Peled
- AAOS96.P.K. Agarwal, B. Aronov, J. O'Rourke, and C. Schevon. Star unfolding of a polytope with applications. SIAM J. Comput., 1996, to appear. Google Scholar
Digital Library
- AHPSV96.P.K. Agarwal, S. Har-Peled, M. Sha.dr, and K. R. Varadarajan. Approximate shortest paths on a convex polytope in three dimensions. Report CS- 1996-12, Dept. Comput. Sci., Duke Univ., Durham, NC, 1996.Google Scholar
- CH96.J. Chen and Y. Han. Shortest paths on a polyhedron; Part I: computing shortest paths. Int. J. Comput. Geom. # Appl., 6(2):127-144, 1996.Google Scholar
- Cla87.K.L. Clarkson. Approximation algorithms for shortest path motion planning. In Proc. 19th Annu. A CM Sympos. Theory Comput., pages 56-65, 1987. Google ScholarDigital Library
- CR87.J. Canny and J. H. Reif. New lower bound techniques for robot motion planning problems. In Proc. P.8th Annu. IEEE Sympoa. Found. Camput. Sci., pages 49-60, 1987.Google ScholarDigital Library
- CSY94.J. Choi, J. SeIlen, and C. K. Yap. Approximate Euclidean shortest path in 3-space. In Proc. l Oth Annu. A CM Sympaa. Camput. Geom., pages 41-48, 1994. Google ScholarDigital Library
- DK85.D.P. Dobkin and D. G. Kirkpatrick. A llnear algorithm for determining the separation of convex polyhedra. J. Algorithma, 6:381-392, 1985.Google ScholarCross Ref
- DK90.D.P. Dobkin and D. G. Kirkpatrick. Determining the separation of preprocessed polyhedra - a unified approach. In Proc. 17th Internat. Colloq. Automata Lang. Program., volume 443 of Lecture Notes in Computer Science, pages 400-413. Springer-Verlag, 1990. Google ScholarDigital Library
- HP97.S. Har-Peled. Constructing approximate shortest path maps in three dimensions, manuscript, 1997.Google Scholar
- HS95.J. Hershberger and S. Suri. Practical methods for approximating shortest paths on a convex polytope in IR3. In Proc. 6th A CM-SIAM Sympos. Discrete Algorithms, pages 447-456, 1995. Google ScholarDigital Library
- MMP87.J.S.B. Mitchell, D. M. Mount, and C. H. Papaclimitriou. The discrete geodesic problem. SIAM J. Comput., 16:647-668, 1987. Google ScholarDigital Library
- Pap85.C. H. Papadimitriou. An algorithm for shortest-path motion in three dimensions. Inform. Process. Lett., 20:259-263, 1985.Google ScholarCross Ref
- Pog73.A.V. Pogorelov. Eztrinsic Geometry of Convez Surfaces, Volume 35 of Translations of Mathematical Monographs. American Mathematical Society, Providence, Rhode Island, 1973.Google Scholar
- RS94.J.H. Reif and J. A. Starer. A single-exponential upper bound for finding shortest paths in three dimensions. J. A CM, 41(5):1013-1019, 1994. Google ScholarDigital Library
- Sha87.M. Sharir. On shortest paths amidst convex polyhedra. SIAM J. Comput., 16:561-572, 1987. Google ScholarDigital Library
- SS86.M. Sharir and A. Schorr. On shortest paths in polyhedral spaces. Siam J. Comput., 15:193- 215, 1986. Google ScholarDigital Library
- VA96.K.R. Varadarajan and P.K. Agarwal. Approximating shortest paths on a polyhedron. manuscript, 1996.Google Scholar
Index Terms
- Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions
Recommendations
Computing Approximate Shortest Paths on Convex Polytopes
The algorithms for computing a shortest path on a polyhedral surface are slow, complicated, and numerically unstable. We have developed and implemented a robust and efficient algorithm for computing approximate shortest paths on a convex polyhedral ...
Convex hulls of spheres and convex hulls of disjoint convex polytopes
Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Approximating shortest paths on a convex polytope in three dimensions
Given a convex polytope P with n faces in ℝ3, points ∈ ∂P, and a parameter 0 < ϵ ≤ 1, we present an algorithm that constructs a path on ∂P from s to t whose length is at most (1 + ϵ)dp(s, t), where dp(s, t) is the length of the shortest path between s ...
Comments