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

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationProceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PublisherAssociation for Computing Machinery (ACM)
Pages483-484
Number of pages2
ISBN (Print)1595933409, 9781595933409
DOIs
StatePublished - 2006
Event22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States
Duration: Jun 5 2006Jun 7 2006

Publication series

NameProceedings of the Annual Symposium on Computational Geometry
Volume2006

Other

Other22nd Annual Symposium on Computational Geometry 2006, SCG'06
CountryUnited States
CitySedona, AZ
Period6/5/066/7/06

Keywords

  • Algorithms
  • Experimentation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions'. Together they form a unique fingerprint.

Cite this