Improved dynamic geodesic nearest neighbor searching in a simple polygon

DOI10.4230/LIPICS.SOCG.2018.4zbMATH Open1489.68336arXiv1803.05765MaRDI QIDQ5115770FDOQ5115770

Frank Staals, Pankaj K. Agarwal, Lars Arge

Publication date: 18 August 2020

Full work available at URL: https://arxiv.org/abs/1803.05765

Recommendations

• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Dynamic geodesic convex hulls in dynamic simple polygons
• Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons
• Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations

zbMATH Keywords

data structuregeodesic distancesimple polygonnearest neighbor searchingshallow cutting

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Applications of random sampling in computational geometry. II
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimal Point Location in a Monotone Subdivision
• Decomposable searching problems I. Static-to-dynamic transformation
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Title not available (Why is that?)
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
• Higher-Order Geodesic Voronoi Diagrams in a Polygonal Domain with Holes
• The furthest-site geodesic Voronoi diagram
• Optimal shortest path queries in a simple polygon
• On the geodesic Voronoi diagram of point sites in a simple polygon
• Reporting points in halfspaces
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• Relative \((p,\varepsilon )\)-approximations in geometry
• A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains
• Dynamic half-space range reporting and its applications
• Title not available (Why is that?)
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• A new data structure for shortest path queries in a simple polygon
• Maintenance of geometric extrema
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
• Exact upper bound on the sum of squared nearest-neighbor distances between points in a rectangle
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Computing geodesic furthest neighbors in simple polygons
• Title not available (Why is that?)
• Dynamic data structures for \(k\)-nearest neighbor queries
• Title not available (Why is that?)

This page was built for publication: Improved dynamic geodesic nearest neighbor searching in a simple polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115770)