Querying two boundary points for shortest paths in a polygonal domain (Q419498): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
Let \({\mathcal P}\) be a polygonal domain (with holes) in the plane with \(n\) corners. The authors present a data structure that allows for the determination of the shortest path between two points on the boundary \(\partial{\mathcal P}\) in \(O(\log{n})\) time. The shortest path \(\gamma_{u,v}\) between two corners \(u,v\) is necessarily a sequence of line segments adjoining pairs of other corner points, whereas the shortest path between two boundary points \(p,q\) is either the line segment \(\overline{pq}\) or the polygonal path formed from \(\overline{pu}\), \(\overline{vq}\), and \(\gamma_{u,v}\) for some \(u,v\). Using a parametrization \(\alpha\) of \(\partial{\mathcal P}\), the authors write the length of such a path between two boundary points as an algebraic surface \(f_{u,v}(s,t)\), where \(p=\alpha(s)\) and \(q=\alpha(t)\). A data structure used to query the shortest path between two boundary points is then obtained from the minimization diagram \({\mathcal M}\) that computes the lower envelope of the collection of all surfaces \(f_{u,v}\) with \(u,v\) corners of \({\mathcal P}\). It is shown that this structure may be precomputed in \(O(n^{5+\epsilon})\) time, and using the same amount of space. The authors further refine this result by providing a method of computing \({\mathcal M}\) in \(O\bigl(n^4\lambda_{65}(n)\log{n}\bigr)\) time and using \(O\bigl(n^4\lambda_{66}(n)\bigr)\) space, where \(\lambda_m(n)\) is the maximum length of a Davenport--Schinzel sequence of order \(m\) on \(n\) values. | |||
Property / review text: Let \({\mathcal P}\) be a polygonal domain (with holes) in the plane with \(n\) corners. The authors present a data structure that allows for the determination of the shortest path between two points on the boundary \(\partial{\mathcal P}\) in \(O(\log{n})\) time. The shortest path \(\gamma_{u,v}\) between two corners \(u,v\) is necessarily a sequence of line segments adjoining pairs of other corner points, whereas the shortest path between two boundary points \(p,q\) is either the line segment \(\overline{pq}\) or the polygonal path formed from \(\overline{pu}\), \(\overline{vq}\), and \(\gamma_{u,v}\) for some \(u,v\). Using a parametrization \(\alpha\) of \(\partial{\mathcal P}\), the authors write the length of such a path between two boundary points as an algebraic surface \(f_{u,v}(s,t)\), where \(p=\alpha(s)\) and \(q=\alpha(t)\). A data structure used to query the shortest path between two boundary points is then obtained from the minimization diagram \({\mathcal M}\) that computes the lower envelope of the collection of all surfaces \(f_{u,v}\) with \(u,v\) corners of \({\mathcal P}\). It is shown that this structure may be precomputed in \(O(n^{5+\epsilon})\) time, and using the same amount of space. The authors further refine this result by providing a method of computing \({\mathcal M}\) in \(O\bigl(n^4\lambda_{65}(n)\log{n}\bigr)\) time and using \(O\bigl(n^4\lambda_{66}(n)\bigr)\) space, where \(\lambda_m(n)\) is the maximum length of a Davenport--Schinzel sequence of order \(m\) on \(n\) values. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jason Hanson / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65D18 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68U05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6036554 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
shortest path query | |||
Property / zbMATH Keywords: shortest path query / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
polygonal domain | |||
Property / zbMATH Keywords: polygonal domain / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Davenport-Schinzel sequence | |||
Property / zbMATH Keywords: Davenport-Schinzel sequence / rank | |||
Normal rank |
Revision as of 21:21, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Querying two boundary points for shortest paths in a polygonal domain |
scientific article |
Statements
Querying two boundary points for shortest paths in a polygonal domain (English)
0 references
18 May 2012
0 references
Let \({\mathcal P}\) be a polygonal domain (with holes) in the plane with \(n\) corners. The authors present a data structure that allows for the determination of the shortest path between two points on the boundary \(\partial{\mathcal P}\) in \(O(\log{n})\) time. The shortest path \(\gamma_{u,v}\) between two corners \(u,v\) is necessarily a sequence of line segments adjoining pairs of other corner points, whereas the shortest path between two boundary points \(p,q\) is either the line segment \(\overline{pq}\) or the polygonal path formed from \(\overline{pu}\), \(\overline{vq}\), and \(\gamma_{u,v}\) for some \(u,v\). Using a parametrization \(\alpha\) of \(\partial{\mathcal P}\), the authors write the length of such a path between two boundary points as an algebraic surface \(f_{u,v}(s,t)\), where \(p=\alpha(s)\) and \(q=\alpha(t)\). A data structure used to query the shortest path between two boundary points is then obtained from the minimization diagram \({\mathcal M}\) that computes the lower envelope of the collection of all surfaces \(f_{u,v}\) with \(u,v\) corners of \({\mathcal P}\). It is shown that this structure may be precomputed in \(O(n^{5+\epsilon})\) time, and using the same amount of space. The authors further refine this result by providing a method of computing \({\mathcal M}\) in \(O\bigl(n^4\lambda_{65}(n)\log{n}\bigr)\) time and using \(O\bigl(n^4\lambda_{66}(n)\bigr)\) space, where \(\lambda_m(n)\) is the maximum length of a Davenport--Schinzel sequence of order \(m\) on \(n\) values.
0 references
shortest path query
0 references
polygonal domain
0 references
Davenport-Schinzel sequence
0 references