Shortest paths for disc obstacles

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

Research output: Chapter in Book/Report/Conference proceedingChapter

16 Scopus citations

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 languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsAntonio Lagan`a, Marina L. Gavrilova, Vipin Kumar, Youngsong Mun, C.J. Kenneth Tan, Osvaldo Gervasi
PublisherSpringer Verlag
Pages62-70
Number of pages9
ISBN (Print)3540220577, 9783540220572
DOIs
StatePublished - 2004 Jan 1

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3045
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Convex hull
  • Dijkstra
  • Disc obstacles
  • Ellipse
  • Geodesic
  • Voronoi diagram

Fingerprint Dive into the research topics of 'Shortest paths for disc obstacles'. Together they form a unique fingerprint.

  • Cite this

    Kim, D. S., Yu, K., Cho, Y., Kim, D., & Yap, C. (2004). Shortest paths for disc obstacles. In A. Lagan`a, M. L. Gavrilova, V. Kumar, Y. Mun, C. J. Kenneth Tan, & O. Gervasi (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 62-70). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3045). Springer Verlag. https://doi.org/10.1007/978-3-540-24767-8_7