English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We devise a data structure that can answer shortest path queries for twoquery points in a polygonal domain $P$ on $n$ vertices. For any $\varepsilon >0$, the space complexity of the data structure is $O(n^{10+\varepsilon })$ andqueries can be answered in $O(\log n)$ time. Alternatively, we can achieve aspace complexity of $O(n^{9+\varepsilon })$ by relaxing the query time to$O(\log^2 n)$. This is the first improvement upon a conference paper by Chiangand Mitchell from 1999. They present a data structure with $O(n^{11})$ spacecomplexity and $O(\log n)$ query time. Our main result can be extended toinclude a space-time trade-off. Specifically, we devise data structures with$O(n^{9+\varepsilon}/\hspace{1pt} \ell^{4 + O(\varepsilon )})$ space complexityand $O(\ell \log^2 n )$ query time, for any integer $1 \leq \ell \leq n$.  Furthermore, we present improved data structures with $O(\log n)$ query timefor the special case where we restrict one (or both) of the query points to lieon the boundary of $P$. When one of the query points is restricted to lie onthe boundary, and the other query point is unrestricted, the space complexitybecomes $O(n^{6+\varepsilon})$. When both query points are on the boundary, thespace complexity is decreased further to $O(n^{4+\varepsilon })$, therebyimproving an earlier result of Bae and Okamoto.

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain