Faster and More Robust Mesh-based Algorithms for Obstacle k-Nearest Neighbour
We are interested in the problem of finding $k$ nearest neighbours in the plane and in the presence of polygonal obstacles ($\textit{OkNN}$). Widely used algorithms for OkNN are based on incremental visibility graphs, which means they require costly and online visibility checking and have worst-case quadratic running time. Recently $\mathbf{Polyanya}$, a fast point-to-point pathfinding algorithm was proposed which avoids the disadvantages of visibility graphs by searching over an alternative data structure known as a navigation mesh. Previously, we adapted $\mathbf{Polyanya}$ to multi-target scenarios by developing two specialised heuristic functions: the $\mathbf{Interval heuristic}$ $h_v$ and the $\mathbf{Target heuristic}$ $h_t$. Though these methods outperform visibility graph algorithms by orders of magnitude in all our experiments they are not robust: $h_v$ expands many redundant nodes when the set of neighbours is small while $h_t$ performs poorly when the set of neighbours is large. In this paper, we propose new algorithms and heuristics for OkNN which perform well regardless of neighbour density.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Deep Fuzzy Optimization for Batch-Size and Nearest Neighbors in Optimal Robot Motion Planning
Efficient motion planning algorithms are essential in robotics. Optimizing essential parameters, such as batch size and nearest neighbor selection in sampling-based methods, can enhance performance in the planning proces…
Robot ManipulationMotion PlanningLGSDF: Continual Global Learning of Signed Distance Fields Aided by Local Updating
Implicit reconstruction of ESDF (Euclidean Signed Distance Field) involves training a neural network to regress the signed distance from any point to the nearest obstacle, which has the advantages of lightweight storage …
Continual Self-Supervised LearningSelf-Supervised LearningLearning Representations for Faster Similarity Search
In high dimensions, the performance of nearest neighbor algorithms depends crucially on structure in the data. While traditional nearest neighbor datasets consisted mostly of hand-crafted feature vectors, an increasing n…
General ClassificationMesh Learning for Classifying Cognitive Processes
A relatively recent advance in cognitive neuroscience has been multi-voxel pattern analysis (MVPA), which enables researchers to decode brain states and/or the type of information represented in the brain during a cognit…
ARCTriFlow: Generating Artist-Like 3D Mesh Topology via Nearest-Vertex Vector Fields
We present TriFlow, a new generative approach for producing compact 3D meshes with artist-like triangle topology directly from input geometry conditions such as signed distance fields. Our key insight is to represent mes…