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

Ovidiu Daescu; Joseph S B Mitchell; Simeon Ntafos; James D. Palmer; Chee K. Yap

doi:10.1145/1137856.1137930

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

Ovidiu Daescu, Joseph S B Mitchell, Simeon Ntafos, James D. Palmer, Chee K. Yap

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
Publisher	Association for Computing Machinery (ACM)
Pages	483-484
Number of pages	2
ISBN (Print)	1595933409, 9781595933409
DOIs	https://doi.org/10.1145/1137856.1137930
State	Published - 2006
Event	22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States Duration: Jun 5 2006 → Jun 7 2006

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry
Volume	2006

Other

Other	22nd Annual Symposium on Computational Geometry 2006, SCG'06
Country/Territory	United States
City	Sedona, AZ
Period	6/5/06 → 6/7/06

Keywords

Algorithms
Experimentation

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/1137856.1137930

Cite this

Daescu, O., Mitchell, J. S. B., Ntafos, S., Palmer, J. D., & Yap, C. K. (2006). Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06 (pp. 483-484). (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1137856.1137930

Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions. / Daescu, Ovidiu; Mitchell, Joseph S B; Ntafos, Simeon et al.
Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Association for Computing Machinery (ACM), 2006. p. 483-484 (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Daescu, O, Mitchell, JSB, Ntafos, S, Palmer, JD & Yap, CK 2006, Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions. in Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Proceedings of the Annual Symposium on Computational Geometry, vol. 2006, Association for Computing Machinery (ACM), pp. 483-484, 22nd Annual Symposium on Computational Geometry 2006, SCG'06, Sedona, AZ, United States, 6/5/06. https://doi.org/10.1145/1137856.1137930

Daescu O, Mitchell JSB, Ntafos S, Palmer JD, Yap CK. Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Association for Computing Machinery (ACM). 2006. p. 483-484. (Proceedings of the Annual Symposium on Computational Geometry). doi: 10.1145/1137856.1137930

Daescu, Ovidiu ; Mitchell, Joseph S B ; Ntafos, Simeon et al. / Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions. Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Association for Computing Machinery (ACM), 2006. pp. 483-484 (Proceedings of the Annual Symposium on Computational Geometry).

@inproceedings{37f9d2fd91624a26bfd4f73b0175d2d2,

title = "Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions",

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.",

keywords = "Algorithms, Experimentation",

author = "Ovidiu Daescu and Mitchell, {Joseph S B} and Simeon Ntafos and Palmer, {James D.} and Yap, {Chee K.}",

year = "2006",

doi = "10.1145/1137856.1137930",

language = "English (US)",

isbn = "1595933409",

series = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "Association for Computing Machinery (ACM)",

pages = "483--484",

booktitle = "Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06",

address = "United States",

note = "22nd Annual Symposium on Computational Geometry 2006, SCG'06 ; Conference date: 05-06-2006 Through 07-06-2006",

}

TY - GEN

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

AU - Daescu, Ovidiu

AU - Mitchell, Joseph S B

AU - Ntafos, Simeon

AU - Palmer, James D.

AU - Yap, Chee K.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - Algorithms

KW - Experimentation

UR - http://www.scopus.com/inward/record.url?scp=33748062983&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748062983&partnerID=8YFLogxK

U2 - 10.1145/1137856.1137930

DO - 10.1145/1137856.1137930

M3 - Conference contribution

AN - SCOPUS:33748062983

SN - 1595933409

SN - 9781595933409

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 483

EP - 484

BT - Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06

PB - Association for Computing Machinery (ACM)

T2 - 22nd Annual Symposium on Computational Geometry 2006, SCG'06

Y2 - 5 June 2006 through 7 June 2006

ER -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this