View in EDS PDF Full Text

SHORTEST PATH QUERIES AMONG WEIGHTED OBSTACLES IN THE RECTILINEAR PLANE.

Saved in:
Bibliographic Details
Title: SHORTEST PATH QUERIES AMONG WEIGHTED OBSTACLES IN THE RECTILINEAR PLANE.
Authors: Chen, Danny Z.1 dchen@cse.nd.edu, Klenk, Kevin S.1 kklenk@cse.nd.edu, Tu, Hung-Yi T.2 hytu@simon.pu.edu.tw
Source: SIAM Journal on Computing. 2000, Vol. 29 Issue 4, p1223. 24p.
Subjects: Data structures, COMSKEE (Computer program language), Computer software, Algorithms
Abstract: We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O(n log&frac32; n) time and O(nlog n) space, where n is the number of obstacle vertices; this data structure enables us to report the length of a shortest path between the source and any query point in O(log n) time, and an actual shortest path in O(log n+k) time, where k is the number of edges on the output path. For the two-point case, we construct a data structure in O(n[SUP2]log[SUP2]n) time and space; this data structure enables us to report the length of a shortest path between two arbitrary query points in O(log[SUP2]n) time, and an actual shortest path in O(log[SUP2]n+k) time. Our work improves and generalizes the previously best-known results on computing rectilinear shortest paths among weighted polygonal obstacles. We also apply our techniques to processing two- point L[SUB1] shortest obstacle-avoiding path queries among arbitrary (i.e., not necessarily rectilinear) polygonal obstacles in the plane. No algorithm for processing two-point shortest path queries among weighted obstacles was previously known. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 10699142
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: SHORTEST PATH QUERIES AMONG WEIGHTED OBSTACLES IN THE RECTILINEAR PLANE.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Chen%2C+Danny+Z%2E%22">Chen, Danny Z.</searchLink><relatesTo>1</relatesTo><i> dchen@cse.nd.edu</i><br /><searchLink fieldCode="AR" term="%22Klenk%2C+Kevin+S%2E%22">Klenk, Kevin S.</searchLink><relatesTo>1</relatesTo><i> kklenk@cse.nd.edu</i><br /><searchLink fieldCode="AR" term="%22Tu%2C+Hung-Yi+T%2E%22">Tu, Hung-Yi T.</searchLink><relatesTo>2</relatesTo><i> hytu@simon.pu.edu.tw</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Computing%22">SIAM Journal on Computing</searchLink>. 2000, Vol. 29 Issue 4, p1223. 24p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Data+structures%22">Data structures</searchLink><br /><searchLink fieldCode="DE" term="%22COMSKEE+%28Computer+program+language%29%22">COMSKEE (Computer program language)</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software%22">Computer software</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O(n log&frac32; n) time and O(nlog n) space, where n is the number of obstacle vertices; this data structure enables us to report the length of a shortest path between the source and any query point in O(log n) time, and an actual shortest path in O(log n+k) time, where k is the number of edges on the output path. For the two-point case, we construct a data structure in O(n[SUP2]log[SUP2]n) time and space; this data structure enables us to report the length of a shortest path between two arbitrary query points in O(log[SUP2]n) time, and an actual shortest path in O(log[SUP2]n+k) time. Our work improves and generalizes the previously best-known results on computing rectilinear shortest paths among weighted polygonal obstacles. We also apply our techniques to processing two- point L[SUB1] shortest obstacle-avoiding path queries among arbitrary (i.e., not necessarily rectilinear) polygonal obstacles in the plane. No algorithm for processing two-point shortest path queries among weighted obstacles was previously known. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=10699142
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/S0097539796307194
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 24
        StartPage: 1223
    Subjects:
      – SubjectFull: Data structures
        Type: general
      – SubjectFull: COMSKEE (Computer program language)
        Type: general
      – SubjectFull: Computer software
        Type: general
      – SubjectFull: Algorithms
        Type: general
    Titles:
      – TitleFull: SHORTEST PATH QUERIES AMONG WEIGHTED OBSTACLES IN THE RECTILINEAR PLANE.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Chen, Danny Z.
      – PersonEntity:
          Name:
            NameFull: Klenk, Kevin S.
      – PersonEntity:
          Name:
            NameFull: Tu, Hung-Yi T.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 02
              Text: 2000
              Type: published
              Y: 2000
          Identifiers:
            – Type: issn-print
              Value: 00975397
          Numbering:
            – Type: volume
              Value: 29
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: SIAM Journal on Computing
              Type: main
ResultId 1