Shortest paths for disc obstacles

Deok Soo Kim; Kwangseok Yu; Youngsong Cho; Donguk Kim; Chee Yap

Shortest paths for disc obstacles

Deok Soo Kim, Kwangseok Yu, Youngsong Cho, Donguk Kim, Chee Yap

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Given a number of obstacles in a plane, the problem of computing a geodesic (or the shortest path) between two points has been studied extensively. However, the case where the obstacles are circular discs has not been explored as much as it deserves. In this paper, we present an algorithm to compute a geodesic among a set of mutually disjoint discs, where the discs can have different radii. We devise two filters, an ellipse filter and a convex hull filter, which can significantly reduce the search space. After filtering, we apply Dijkstra's algorithm to the remaining discs.

Original language	English (US)
Pages (from-to)	62-70
Number of pages	9
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3045
State	Published - Dec 1 2004

Keywords

Convex hull
Dijkstra
Disc obstacles
Ellipse
Geodesic
Voronoi diagram

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Cite this

@article{3bc14a6442354158b7cd10902c360b22,

title = "Shortest paths for disc obstacles",

abstract = "Given a number of obstacles in a plane, the problem of computing a geodesic (or the shortest path) between two points has been studied extensively. However, the case where the obstacles are circular discs has not been explored as much as it deserves. In this paper, we present an algorithm to compute a geodesic among a set of mutually disjoint discs, where the discs can have different radii. We devise two filters, an ellipse filter and a convex hull filter, which can significantly reduce the search space. After filtering, we apply Dijkstra's algorithm to the remaining discs.",

keywords = "Convex hull, Dijkstra, Disc obstacles, Ellipse, Geodesic, Voronoi diagram",

author = "Kim, {Deok Soo} and Kwangseok Yu and Youngsong Cho and Donguk Kim and Chee Yap",

year = "2004",

month = dec,

day = "1",

language = "English (US)",

volume = "3045",

pages = "62--70",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - Shortest paths for disc obstacles

AU - Kim, Deok Soo

AU - Yu, Kwangseok

AU - Cho, Youngsong

AU - Kim, Donguk

AU - Yap, Chee

PY - 2004/12/1

Y1 - 2004/12/1

N2 - Given a number of obstacles in a plane, the problem of computing a geodesic (or the shortest path) between two points has been studied extensively. However, the case where the obstacles are circular discs has not been explored as much as it deserves. In this paper, we present an algorithm to compute a geodesic among a set of mutually disjoint discs, where the discs can have different radii. We devise two filters, an ellipse filter and a convex hull filter, which can significantly reduce the search space. After filtering, we apply Dijkstra's algorithm to the remaining discs.

AB - Given a number of obstacles in a plane, the problem of computing a geodesic (or the shortest path) between two points has been studied extensively. However, the case where the obstacles are circular discs has not been explored as much as it deserves. In this paper, we present an algorithm to compute a geodesic among a set of mutually disjoint discs, where the discs can have different radii. We devise two filters, an ellipse filter and a convex hull filter, which can significantly reduce the search space. After filtering, we apply Dijkstra's algorithm to the remaining discs.

KW - Convex hull

KW - Dijkstra

KW - Disc obstacles

KW - Ellipse

KW - Geodesic

KW - Voronoi diagram

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

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

M3 - Article

AN - SCOPUS:31344457577

SN - 0302-9743

VL - 3045

SP - 62

EP - 70

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

Shortest paths for disc obstacles

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this