1-Link shortest paths in weighted regions

Ovidiu Daescu; James D. Palmer

doi:10.1145/1064092.1064155

1-Link shortest paths in weighted regions

Ovidiu Daescu, James D. Palmer

Informatics, Computing, and Cyber Systems, School of

Research output: Contribution to conference › Paper › peer-review

Abstract

We illustrate the Link Solver software for computing 1-link shortest paths in weighted regions. The Link Solver implements a prune-and-search method that can be used to approximate an optimal solution within a user specified precision. The theoretical foundation of the method is a result stating that an optimal solution goes through a vertex of the subdivision. This result provides a way to discretize the problem with respect to vertices of interest which in turn leads to efficient algorithms.

Original language	English (US)
Pages	378-379
Number of pages	2
DOIs	https://doi.org/10.1145/1064092.1064155
State	Published - 2005
Event	21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italy Duration: Jun 6 2005 → Jun 8 2005

Other

Other	21st Annual Symposium on Computational Geometry, SCG'05
Country/Territory	Italy
City	Pisa
Period	6/6/05 → 6/8/05

Keywords

Algorithms
Experimentation

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/1064092.1064155

Cite this

@conference{2f08e28c8af043fc8507daf84ac1f510,

title = "1-Link shortest paths in weighted regions",

abstract = "We illustrate the Link Solver software for computing 1-link shortest paths in weighted regions. The Link Solver implements a prune-and-search method that can be used to approximate an optimal solution within a user specified precision. The theoretical foundation of the method is a result stating that an optimal solution goes through a vertex of the subdivision. This result provides a way to discretize the problem with respect to vertices of interest which in turn leads to efficient algorithms.",

keywords = "Algorithms, Experimentation",

author = "Ovidiu Daescu and Palmer, {James D.}",

year = "2005",

doi = "10.1145/1064092.1064155",

language = "English (US)",

pages = "378--379",

note = "21st Annual Symposium on Computational Geometry, SCG'05 ; Conference date: 06-06-2005 Through 08-06-2005",

}

TY - CONF

T1 - 1-Link shortest paths in weighted regions

AU - Daescu, Ovidiu

AU - Palmer, James D.

PY - 2005

Y1 - 2005

N2 - We illustrate the Link Solver software for computing 1-link shortest paths in weighted regions. The Link Solver implements a prune-and-search method that can be used to approximate an optimal solution within a user specified precision. The theoretical foundation of the method is a result stating that an optimal solution goes through a vertex of the subdivision. This result provides a way to discretize the problem with respect to vertices of interest which in turn leads to efficient algorithms.

AB - We illustrate the Link Solver software for computing 1-link shortest paths in weighted regions. The Link Solver implements a prune-and-search method that can be used to approximate an optimal solution within a user specified precision. The theoretical foundation of the method is a result stating that an optimal solution goes through a vertex of the subdivision. This result provides a way to discretize the problem with respect to vertices of interest which in turn leads to efficient algorithms.

KW - Algorithms

KW - Experimentation

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

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

U2 - 10.1145/1064092.1064155

DO - 10.1145/1064092.1064155

M3 - Paper

SP - 378

EP - 379

T2 - 21st Annual Symposium on Computational Geometry, SCG'05

Y2 - 6 June 2005 through 8 June 2005

ER -

1-Link shortest paths in weighted regions

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this