Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions

Full text

Pdf (595 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twenty-second annual symposium on Computational geometry table of contents

Sedona, Arizona, USA

SESSION: Multimedia abstracts table of contents

Pages: 483 - 484

Year of Publication: 2006

ISBN:1-59593-340-9

Authors

Ovidiu Daescu	The University of Texas at Dallas, Richardson, TX
Joseph S. B. Mitchell	Stony Brook University, Stony Brook, NY
Simeon Ntafos	The University of Texas at Dallas, Richardson, TX
James D. Palmer	The University of Texas at Dallas, Richardson, TX
Chee K. Yap	New York University, New York, NY

Sponsors

ACM: Association for Computing Machinery
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): 5, Downloads (12 Months): 27, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	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/1137856.1137930 What is a DOI?

ABSTRACT

This video illustrates the k-LinkSolver software for computing k-link shortest paths in weighted regions. The k-LinkSolver implements methods to find paths of length at most (1+ε) times the length of a shortest k-link path, for any fixed ε>0, and having at most 2k−1 links. The methods implemented are an improvement over the previously known (1+ε)-approximation algorithms, which guarantee at most 5k−2 links.

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	L. Aleksandrov , A. Maheshwari , J.-R. Sack, Determining approximate shortest paths on weighted polyhedral surfaces, Journal of the ACM (JACM), v.52 n.1, p.25-53, January 2005 [doi>10.1145/1044731.1044733]
	2	D. Z. Chen, O. Daescu, X. Hu, X. Wu, and J. Xu. Determining an optimal penetration among weighted regions in two and three dimensions. Journal of Combinatorial Optimization, 5(1):59--79, 2001.
	3	Ovidiu Daescu, Improved Optimal Weighted Links Algorithms, Proceedings of the International Conference on Computational Science-Part III, p.65-74, April 21-24, 2002
	4	O. Daescu, J. S. B. Mitchell, S. Ntafos, J. D. Palmer, and C. K. Yap. k-link shortest paths in weighted subdivisions. In Proc. 9th Workshop Algorithms Data Struct., Vol 3608 of Lecture Notes Comput. Sci., pages 325--337. Springer-Verlag, 2005.
	5	Joseph S. B. Mitchell , Christos H. Papadimitriou, The weighted region problem: finding shortest paths through a weighted planar subdivision, Journal of the ACM (JACM), v.38 n.1, p.18-73, Jan. 1991 [doi>10.1145/102782.102784]