Optimal Search in Planar Subdivisions

Cited in

(only showing first 100 items - show all)

Closest-pair queries and minimum-weight queries are equivalent for squares
An optimal algorithm for computing visible nearest foreign neighbors among colored line segments
How to pack directed acyclic graphs into small blocks
Dynamic Trees and Dynamic Point Location
Solving related two- and three-dimensional linear programming problems in logarithmic time
On fast planning of suboptimal paths amidst polygonal obstacles in plane
Locating two obnoxious facilities using the weighted maximin criterion
Efficient visibility queries in simple polygons
An Improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem
Storing the subdivision of a polyhedral surface
Hausdorff approximation of 3D convex polytopes
Sorting weighted distances with applications to objective function evaluations in single facility location problems.
Dilation-Optimal Edge Deletion in Polygonal Cycles
Space-efficient functional offline-partially-persistent trees with applications to planar point location
An approximate algorithm for computing multidimensional convex hulls
Efficient computation of rectilinear geodesic Voronoi neighbor in presence of obstacles
Derandomizing an output-sensitive convex hull algorithm in three dimensions
Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra
An algorithmic approach to some problems in terrain navigation
Reporting and counting segment intersections
Time-space trade-offs for triangulations and Voronoi diagrams
Line arrangements and range search
A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
Voronoi diagrams with barriers and on polyhedra for minimal path planning
Geometric complexity of some location problems
Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
Time-space trade-offs for triangulations and Voronoi diagrams
Finding effective ``Force targets for two-dimensional, multifinger frictional grips
Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\)
Rectilinear short path queries among rectangular obstacles
\((1+\varepsilon)\)-ANN data structure for curves via subspaces of bounded doubling dimension
Shortest paths among transient obstacles
Efficient ray shooting and hidden surface removal
An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³
On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
Generalized Delaunay triangulation for planar graphs
An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments
Distance-sensitive planar point location
Decomposing the boundary of a nonconvex polyhedron
Query point visibility computation in polygons with holes
A linear-time algorithm for computing the Voronoi diagram of a convex polygon
Establishing order in planar subdivisions
Algorithms for bivariate zonoid depth
Online \(k\)-color spanning disk problems
Approximating points by a piecewise linear function
An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs
An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
\(L_ 1\) shortest paths among polygonal obstacles in the plane
Variable resolution triangulations
On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
Computing \(L_1\) shortest paths among polygonal obstacles in the plane
Visibility and ray shooting queries in polygonal domains
Construction of triangle meshes from images at multiple scales based on median error metric
Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
ON GEOMETRIC PATH QUERY PROBLEMS
A general approach for cache-oblivious range reporting and approximate range counting
A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
The power of geometric duality
Linear space data structures for two types of range search
Maintaining multiple representations of dynamic data structures
Computing the external geodesic diameter of a simple polygon
RESTRICTED MESH SIMPLIFICATION USING EDGE CONTRACTIONS
Local routing algorithms on Euclidean spanners with small diameter
Algorithms for subpath convex hull queries and ray-shooting among segments
On condorcet and median points of simple rectilinear polygons
Implicitly representing arrangements of lines or segments
Dilation-optimal edge deletion in polygonal cycles
An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model
Triangulating a simple polygon in linear time
Hierarchy of surface models and irreducible triangulations.
Stabbing circles for sets of segments in the plane
Orthogonal point location and rectangle stabbing queries in 3-d
On the line-separable unit-disk coverage and related problems
Computing the \(k\)-visibility region of a point in a polygon
Quickest visibility queries in polygonal domains
Optimal cooperative search in fractional cascaded data structures
Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
Ray shooting in polygons using geodesic triangulations
Graphics in flatland revisited
Low complexity algorithms for optimal consumer push-pull partial covering in the plane
Parallel construction of subdivision hierarchies
Randomized incremental construction of Delaunay and Voronoi diagrams
Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology
Light edges in degree-constrained graphs
Faster goal-oriented shortest path search for bulk and incremental detailed routing
Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
Point set stratification and Delaunay depth
Reverse shortest path problem in weighted unit-disk graphs
Shortest monotone descent path problem in polyhedral terrain
On the complexity of approximating and illuminating three-dimensional convex polyhedra
Shortest Path Queries in Polygonal Domains
Computing the visibility map of fat objects
A fast algorithm for point-location in a finite element mesh
A parallel algorithm for constructing projection polyhedra
Shortest paths in the plane with obstacle violations
Computing a median point of a simple rectilinear polygon
Near optimal line segment queries in simple polygons
Expected asymptotically optimal planar point location
Adaptive planar point location

This page was built for publication: Optimal Search in Planar Subdivisions

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