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 are interested in the problem of finding $k$ nearest neighbours in theplane and in the presence of polygonal obstacles ($\textit{OkNN}$). Widely usedalgorithms for OkNN are based on incremental visibility graphs, which meansthey require costly and online visibility checking and have worst-casequadratic running time. Recently $\mathbf{Polyanya}$, a fast point-to-pointpathfinding algorithm was proposed which avoids the disadvantages of visibilitygraphs by searching over an alternative data structure known as a navigationmesh. Previously, we adapted $\mathbf{Polyanya}$ to multi-target scenarios bydeveloping two specialised heuristic functions: the $\mathbf{Intervalheuristic}$ $h_v$ and the $\mathbf{Target heuristic}$ $h_t$. Though thesemethods outperform visibility graph algorithms by orders of magnitude in allour experiments they are not robust: $h_v$ expands many redundant nodes whenthe set of neighbours is small while $h_t$ performs poorly when the set ofneighbours is large. In this paper, we propose new algorithms and heuristicsfor OkNN which perform well regardless of neighbour density.

Faster and More Robust Mesh-based Algorithms for Obstacle k-Nearest Neighbour