Optimal Search in Planar Subdivisions
From MaRDI portal
Publication:3967063
DOI10.1137/0212002zbMath0501.68034OpenAlexW2126876121WikidataQ56288797 ScholiaQ56288797MaRDI QIDQ3967063
Publication date: 1983
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/b2e66a427d18701f71818e9d72a27416e373c80e
planar graphsanalysis of algorithmscomputational geometrypoint locationhierarchical searchpartition of the plane into polygonal regions
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (only showing first 100 items - show all)
Rooted Uniform Monotone Minimum Spanning Trees ⋮ Computing the intersection-depth to polyhedra ⋮ Time-Space Trade-offs for Triangulations and Voronoi Diagrams ⋮ Approximating points by a piecewise linear function ⋮ An optimal algorithm for computing visible nearest foreign neighbors among colored line segments ⋮ Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology ⋮ On condorcet and median points of simple rectilinear polygons ⋮ Graphics in flatland revisited ⋮ Input-sensitive compliant motion in the plane ⋮ On the complexity of approximating and illuminating three-dimensional convex polyhedra ⋮ Unnamed Item ⋮ Efficient approximate shortest-path queries among isothetic rectangular obstacles ⋮ Practical distribution-sensitive point location in triangulations ⋮ Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance ⋮ DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES ⋮ Adaptive Point Location in Planar Convex Subdivisions ⋮ Reverse shortest path problem in weighted unit-disk graphs ⋮ Shortest paths among transient obstacles ⋮ A simple but effective improvement to the plumb-line algorithm ⋮ Faster goal-oriented shortest path search for bulk and incremental detailed routing ⋮ RESTRICTED MESH SIMPLIFICATION USING EDGE CONTRACTIONS ⋮ Spanners for Directed Transmission Graphs ⋮ Shortest paths in the plane with obstacle violations ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ Computing constrained minimum-width annuli of point sets ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane ⋮ Online \(k\)-color spanning disk problems ⋮ An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs ⋮ Efficient computation of the geodesic Voronoi diagram of points in a simple polygon ⋮ An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3 ⋮ Space-efficient functional offline-partially-persistent trees with applications to planar point location ⋮ Local routing algorithms on Euclidean spanners with small diameter ⋮ Shortest Path Queries in Polygonal Domains ⋮ Unnamed Item ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Separating a polyhedron by one translation from a set of obstacles ⋮ Three problems about simple polygons ⋮ How to pack directed acyclic graphs into small blocks ⋮ Unnamed Item ⋮ Dilation-Optimal Edge Deletion in Polygonal Cycles ⋮ On Combinatorial Depth Measures ⋮ Algorithms for bivariate zonoid depth ⋮ On polyhedra induced by point sets in space ⋮ Query point visibility computation in polygons with holes ⋮ Query-point visibility constrained shortest paths in simple polygons ⋮ New upper bounds for generalized intersection searching problems ⋮ WALKING IN A TRIANGULATION ⋮ A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions ⋮ An optimal-time algorithm for shortest paths on a convex polytope in three dimensions ⋮ Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time. ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ Visibility and ray shooting queries in polygonal domains ⋮ Computing largest empty circles with location constraints ⋮ An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model ⋮ Computing the visibility map of fat objects ⋮ \(L_{1}\) shortest path queries in simple polygons ⋮ ON GEOMETRIC PATH QUERY PROBLEMS ⋮ The first subquadratic algorithm for complete linkage clustering ⋮ Spanning trees with low crossing number ⋮ PARETO ENVELOPES IN SIMPLE POLYGONS ⋮ Unnamed Item ⋮ I/O-efficient point location using persistent B-trees ⋮ Dynamic planar point location with optimal query time ⋮ An Improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem ⋮ External memory planar point location with logarithmic updates ⋮ Quickest visibility queries in polygonal domains ⋮ Dynamic Trees and Dynamic Point Location ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ Adaptive Planar Point Location ⋮ Locating two obnoxious facilities using the weighted maximin criterion ⋮ Connectivity and stretch factor trade-offs in wireless sensor networks with directional antennae ⋮ Weak visibility queries of line segments in simple polygons ⋮ On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles ⋮ Time-space trade-offs for triangulations and Voronoi diagrams ⋮ Generalized Delaunay triangulation for planar graphs ⋮ Computing circular separability ⋮ Closest-pair queries and minimum-weight queries are equivalent for squares ⋮ Efficient ray shooting and hidden surface removal ⋮ Ray shooting in polygons using geodesic triangulations ⋮ The power of geometric duality ⋮ An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments ⋮ Distance-sensitive planar point location ⋮ I/O-efficient dynamic planar point location ⋮ Expected asymptotically optimal planar point location ⋮ Algorithms for graphs of bounded treewidth via orthogonal range searching ⋮ Solving related two- and three-dimensional linear programming problems in logarithmic time ⋮ Derandomizing an output-sensitive convex hull algorithm in three dimensions ⋮ An efficient parallel algorithm for finding rectangular duals of plane triangular graphs ⋮ Rectilinear short path queries among rectangular obstacles ⋮ Geometric complexity of some location problems ⋮ Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons ⋮ Decomposition and intersection of simple splinegons ⋮ Line arrangements and range search ⋮ Optimal randomized incremental construction for guaranteed logarithmic planar point location ⋮ A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs ⋮ Optimal cooperative search in fractional cascaded data structures ⋮ A compact piecewise-linear Voronoi diagram for convex sites in the plane ⋮ On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees ⋮ On fast planning of suboptimal paths amidst polygonal obstacles in plane ⋮ The shortest watchtower and related problems for polyhedral terrains
This page was built for publication: Optimal Search in Planar Subdivisions
