Optimal Search in Planar Subdivisions

Cited in

(only showing first 100 items - show all)

Computing largest empty circles with location constraints
On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
Implicitly representing arrangements of lines or segments
Efficient visibility queries in simple polygons
Spanning trees with low crossing number
Generalized Delaunay triangulation for planar graphs
Stabbing circles for sets of segments in the plane
Hierarchy of surface models and irreducible triangulations.
Query point visibility computation in polygons with holes
Linear space data structures for two types of range search
\(L_ 1\) shortest paths among polygonal obstacles in the plane
Maintaining multiple representations of dynamic data structures
Computational geometry in a curved world
Computing the external geodesic diameter of a simple polygon
Relative \((p,\varepsilon )\)-approximations in geometry
Linear time approximation of 3D convex polytopes
On Combinatorial Depth Measures
An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments
Distance-sensitive planar point location
Dynamic Trees and Dynamic Point Location
Local routing algorithms on Euclidean spanners with small diameter
An incremental reconstruction method for dynamic planar point location
Tight bounds for connecting sites across barriers
A compact piecewise-linear Voronoi diagram for convex sites in the plane
Input-sensitive compliant motion in the plane
A multifacility location problem on median spaces
Triangulating a simple polygon in linear time
An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
I/O-efficient point location using persistent B-trees
Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\)
An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
Shortest Path Queries in Polygonal Domains
Ray shooting in polygons using geodesic triangulations
Light edges in degree-constrained graphs
A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
Decomposing the boundary of a nonconvex polyhedron
Proximity problems for points on a rectilinear plane with rectangular obstacles
Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
Decomposition and intersection of simple splinegons
Reporting and counting segment intersections
Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon
Dynamic planar point location with optimal query time
An algorithmic approach to some problems in terrain navigation
Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
Randomized incremental construction of Delaunay and Voronoi diagrams
Algorithms for high dimensional stabbing problems
Diameter, width, closest line pair, and parametric searching
Three problems about simple polygons
An approximate algorithm for computing multidimensional convex hulls
On polyhedra induced by point sets in space
Partitioning arrangements of lines. II: Applications
Bottleneck detour tree of points on a path
Storing the subdivision of a polyhedral surface
Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology
The power of geometric duality
A linear-time algorithm for computing the Voronoi diagram of a convex polygon
New upper bounds for generalized intersection searching problems
The power of geometric duality revisited
Outlier respecting points approximation
The shortest watchtower and related problems for polyhedral terrains
I/O-efficient path traversal in succinct planar graphs
Algorithms for graphs of bounded treewidth via orthogonal range searching
Geometric complexity of some location problems
Expected asymptotically optimal planar point location
ON GEOMETRIC PATH QUERY PROBLEMS
On separating two simple polygons by a single translation
Locating two obnoxious facilities using the weighted maximin criterion
Efficient ray shooting and hidden surface removal
Optimal randomized incremental construction for guaranteed logarithmic planar point location
Shortest monotone descent path problem in polyhedral terrain
WALKING IN A TRIANGULATION
Computing a median point of a simple rectilinear polygon
On rectilinear link distance
Parallel construction of subdivision hierarchies
Semi-Lagrangian methods for level set equations
Derandomizing an output-sensitive convex hull algorithm in three dimensions
Computing circular separability
On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
Computing the intersection-depth to polyhedra
Sorting weighted distances with applications to objective function evaluations in single facility location problems.
Visibility and ray shooting queries in polygonal domains
Approximating points by a piecewise linear function
Triangulating a nonconvex polytope
A fast algorithm for point-location in a finite element mesh
Efficient approximate shortest-path queries among isothetic rectangular obstacles
On fast planning of suboptimal paths amidst polygonal obstacles in plane
An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs
On the complexity of approximating and illuminating three-dimensional convex polyhedra
Query-point visibility constrained shortest paths in simple polygons
Efficient computation of the geodesic Voronoi diagram of points in a simple polygon
Optimal cooperative search in fractional cascaded data structures
Finding extreme points in three dimensions and solving the post-office problem in the plane
A near-optimal algorithm for shortest paths among curved obstacles in the plane
Faster goal-oriented shortest path search for bulk and incremental detailed routing
Applications of generalized matrix searching to geometric algorithms
Dynamic planar point location with optimal query time (extended abstract)
How to pack directed acyclic graphs into small blocks
A workbench for computational geometry
A fast algorithm for computing irreducible triangulations of closed surfaces in \(\mathbb{E}^d\)

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)