Computing approximate shortest paths on convex polytopes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing approximate shortest paths on convex polytopes

Full text

Pdf (1.19 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the sixteenth annual symposium on Computational geometry table of contents

Clear Water Bay, Kowloon, Hong Kong

Pages: 270 - 279

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

Pankaj K. Agarwal	Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NC
Sariel Har-Peled	Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NC
Meetesh Karia	Trilogy Software, Inc., 6034 W. Courtyard Drive, Austin, TX

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 22, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/336154.336213 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. K. Agarwal and S. Har-Peled. Approximating shortest-path of terrains. In preparation.
	2	P. K. Agarwal, S. Har-Peled, and M. Karia. Shortest path -- demo program, http://www, cs. duke. edu/~ sariei/papers/99/nav/nav, html~ 1999.
	3	Pankaj K. Agarwal , Sariel Har-Peled , Micha Sharir , Kasturi R. Varadarajan, Approximating shortest paths on a convex polytope in three dimensions, Journal of the ACM (JACM), v.44 n.4, p.567-584, July 1997 [doi>10.1145/263867.263869]
	4	Lyudmil Aleksandrov , Mark Lanthier , Anil Maheshwari , Jörg-Rüdiger Sack, An epsilon-Approximation for Weighted Shortest Paths on Polyhedral Surfaces, Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, p.11-22, July 08-10, 1998
	5	R. Alexander and N. Rowe. Path planning by optimal-path-map construction for homogeneouscost two-dimensional regions. In Proc. IEEE Internat. Conf. Robot. Aurora., 1990.
	6	Jindong Chen , Yijie Han, Shortest paths on a polyhedron, Proceedings of the sixth annual symposium on Computational geometry, p.360-369, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98601]
	7	D. P. Dobkin and D. G. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra. J. Algorithms, 6:381-392, 1985.
	8	D. Douglas. Least cost path in geographic information systems. Research note no. 61, Department of Geography, University of Ottawa, Ottawa, Ontario, Aug. 1993.
	9	R. M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory, i0(3):227-236, 1974.
	10	Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
	11	S. Har-Peled. Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions. Discrete Comput. Geom., 21:216-231, 1999.
	12	G. Hardy and E. Wright. The Theory of Numbers. Oxford University Press, London, England, 4th edition, 1965.
	13	P. Heckbert and M. Garland. Survey of polygonal surface simplification algorithms. Technical report, CMU-CS, 1997. http: //www.cs.cmu. edu / ~ garland/Papers / simp. pdf.
	14	J. Hershberger and S. Suri. Practical methods for approximating shortest paths on a convex polytope in ~a. Comput. Geom. Theory Appl., 10(1):31-46, 1998.
	15	P. Johansson. On a weighted distance model for injection moulding. LinkSping Studies in Science and Technology, Thesis No. 604 LiU-TEK-LIC-1997:05, Division of Applied Mathematics, LinkSping University, LinkSping, Sweden, Feb. 1997.
	16	Sanjiv Kapoor, Efficient computation of geodesic shortest paths, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.770-779, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301449]
	17	M. Kindl, M. Shing, and N. Rowe. A stochastic approach to the weighted-region problem, I: The design of the path annealing algorithm. Technical report, Computer Science, U.S. Naval Postgraduate School, Monterey, CA, 1991.
	18	M. Kindl, M. Shing, and N. Rowe. A stochastic approach to the weighted-region problem, II: Performance enhancement techniques and experimental results. Technical report, Computer Science, U.S. Naval Postgraduate School, Monterey, CA, 1991.
	19	Mark Lanthier , Anil Maheshwari , Jörg-Rüdiger Sack, Approximating weighted shortest paths on polyhedral surfaces, Proceedings of the thirteenth annual symposium on Computational geometry, p.274-283, June 04-06, 1997, Nice, France [doi>10.1145/262839.262984]
	20	M. J. Longtin. Cover and concealment in ModSAF. In Proc. 4th Conf. on Computer Generated Forces and Behavioral Representation, pages 239-247, 1994.
	21	M. J. Longtin and D. Megherbi. Concealed routes in ModSAF. In Proc. 5th Conf. on Computer Generated Forces and Behavioral Representation, pages 305-313, 1995.
	22	Christian S. Mata , Joseph S. B. Mitchell, A new algorithm for computing shortest paths in weighted planar subdivisions (extended abstract), Proceedings of the thirteenth annual symposium on Computational geometry, p.264-273, June 04-06, 1997, Nice, France [doi>10.1145/262839.262983]
	23	Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
	24	Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
	25	J. S. B. Mitchell. An algorithmic approach to some problems in terrain navigation. In S. S. Iyengar and A. Elfes, editors, Autonomous Mobile Robots: Perception, Mapping, and Navigation, pages 408-427. IEEE Computer Society Press, Los Alamitos, CA, 1991.
	26	C. Papadimitriou. Efficient search for rationals. Info. Process. Left., 8(1):1-4, 1979.
	27	C. H. Papadimitriou. An algorithm for shortest-path motion in three dimensions. Inform. Process. Left., 20:259-263, 1985.
	28	R. F. Richbourg, N. C. Rowe, M. J. Zyda, and R. McGhee. Solving global two-dimensional routing problems using Snell's law. In Proc. IEEE Internat. Conf. Robot. Aurora., pages 1631-1636, 1987.
	29	Micha Sharir , Amir Schorr, On shortest paths in polyhedral spaces, SIAM Journal on Computing, v.15 n.1, p.193-215, Feb. 1986 [doi>10.1137/0215014]
	30	Kasturi R. Varadarajan , Pankaj K. Agarwal, Approximating Shortest Paths on a Nonconvex Polyhedron, SIAM Journal on Computing, v.30 n.4, p.1321-1340, 2000 [doi>10.1137/S0097539799352759]
	31	W. Warntz. Transportation, social physics, and the law of refraction. The Professional Geographer, 9(4):2-7, 1957.

CITED BY 2

	Shi-Qing Xin , Guo-Jin Wang, Efficiently determining a locally exact shortest path on polyhedral surfaces, Computer-Aided Design, v.39 n.12, p.1081-1090, December, 2007
	Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan , Michiel Smid, Approximate distance oracles for geometric spanners, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-34, March 2008