Optimal Search in Planar Subdivisions

Cited In (only showing first 100 items - show all)

Dynamic Trees and Dynamic Point Location
Locating two obnoxious facilities using the weighted maximin criterion
Efficient visibility queries in simple polygons
Storing the subdivision of a polyhedral surface
Sorting weighted distances with applications to objective function evaluations in single facility location problems.
An approximate algorithm for computing multidimensional convex hulls
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
Reporting and counting segment intersections
An algorithmic approach to some problems in terrain navigation
Geometric complexity of some location problems
Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\)
Efficient ray shooting and hidden surface removal
On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
Generalized Delaunay triangulation for planar graphs
Query point visibility computation in polygons with holes
An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments
Distance-sensitive planar point location
A linear-time algorithm for computing the Voronoi diagram of a convex polygon
Approximating points by a piecewise linear function
An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
ON GEOMETRIC PATH QUERY PROBLEMS
On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
Visibility and ray shooting queries in polygonal domains
\(L_ 1\) shortest paths among polygonal obstacles in the plane
Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
Weak visibility queries of line segments in simple polygons
Local routing algorithms on Euclidean spanners with small diameter
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
Implicitly representing arrangements of lines or segments
Stabbing circles for sets of segments in the plane
Hierarchy of surface models and irreducible triangulations.
Triangulating a simple polygon in linear time
Ray shooting in polygons using geodesic triangulations
Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology
Parallel construction of subdivision hierarchies
Light edges in degree-constrained graphs
Randomized incremental construction of Delaunay and Voronoi diagrams
Shortest Path Queries in Polygonal Domains
Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
Shortest monotone descent path problem in polyhedral terrain
Expected asymptotically optimal planar point location
Computing a median point of a simple rectilinear polygon
An incremental reconstruction method for dynamic planar point location
Three problems about simple polygons
On polyhedra induced by point sets in space
Relative \((p,\varepsilon )\)-approximations in geometry
Dynamic planar point location with optimal query time
Algorithms for high dimensional stabbing problems
A compact piecewise-linear Voronoi diagram for convex sites in the plane
The shortest watchtower and related problems for polyhedral terrains
Optimal randomized incremental construction for guaranteed logarithmic planar point location
WALKING IN A TRIANGULATION
Computational geometry in a curved world
Computing the intersection-depth to polyhedra
Decomposition and intersection of simple splinegons
Triangulating a nonconvex polytope
Tight bounds for connecting sites across barriers
Computing circular separability
Spanning trees with low crossing number
On Combinatorial Depth Measures
Input-sensitive compliant motion in the plane
A multifacility location problem on median spaces
New upper bounds for generalized intersection searching problems
Algorithms for graphs of bounded treewidth via orthogonal range searching
On rectilinear link distance
Linear time approximation of 3D convex polytopes
An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
The power of geometric duality revisited
On separating two simple polygons by a single translation
Semi-Lagrangian methods for level set equations
I/O-efficient point location using persistent B-trees
Partitioning arrangements of lines. II: Applications
Bottleneck detour tree of points on a path
Outlier respecting points approximation
I/O-efficient path traversal in succinct planar graphs
Computing largest empty circles with location constraints
Decomposing the boundary of a nonconvex polyhedron
Proximity problems for points on a rectilinear plane with rectangular obstacles
Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon
Diameter, width, closest line pair, and parametric searching
How to pack directed acyclic graphs into small blocks
Closest-pair queries and minimum-weight queries are equivalent for squares
An Improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem
Solving related two- and three-dimensional linear programming problems in logarithmic time
On fast planning of suboptimal paths amidst polygonal obstacles in plane
Dilation-Optimal Edge Deletion in Polygonal Cycles
Space-efficient functional offline-partially-persistent trees with applications to planar point location
Hausdorff approximation of 3D convex polytopes
Efficient computation of rectilinear geodesic Voronoi neighbor in presence of obstacles
Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra
Time-space trade-offs for triangulations and Voronoi diagrams
Time-space trade-offs for triangulations and Voronoi diagrams
Voronoi diagrams with barriers and on polyhedra for minimal path planning
Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
Line arrangements and range search

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)