Optimal Search in Planar Subdivisions

DOI10.1137/0212002zbMath0501.68034OpenAlexW2126876121WikidataQ56288797 ScholiaQ56288797MaRDI QIDQ3967063

David G. Kirkpatrick

Publication date: 1983

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b2e66a427d18701f71818e9d72a27416e373c80e

zbMATH Keywords

planar graphsanalysis of algorithmscomputational geometrypoint locationhierarchical searchpartition of the plane into polygonal regions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

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 ℝ³, 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, 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, Establishing order in planar subdivisions, An algorithmic approach to some problems in terrain navigation, A multifacility location problem on median spaces, A fast algorithm for point-location in a finite element mesh, Shortest monotone descent path problem in polyhedral terrain, Parallel construction of subdivision hierarchies, Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\), Randomized approximation algorithms for planar visibility counting problem, Near optimal line segment queries in simple polygons, Range queries on uncertain data, A fast algorithm for computing irreducible triangulations of closed surfaces in \(\mathbb{E}^d\), Relative \((p,\varepsilon )\)-approximations in geometry, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Computational geometry in a curved world, Applications of generalized matrix searching to geometric algorithms, Geometric path problems with violations, Triangulating a nonconvex polytope, Dynamic planar point location with optimal query time, Algorithms for high dimensional stabbing problems, Partitioning arrangements of lines. II: Applications, Sorting weighted distances with applications to objective function evaluations in single facility location problems., Hierarchy of surface models and irreducible triangulations., Orthogonal drawings of graphs for the automation of VLSI circuit design, Triangulating a simple polygon in linear time, Deferred data structure for the nearest neighbor problem, Randomized incremental construction of Delaunay and Voronoi diagrams, Bottleneck detour tree of points on a path, Finding effective ``Force targets for two-dimensional, multifinger frictional grips, \(L_ 1\) shortest paths among polygonal obstacles in the plane, Stabbing circles for sets of segments in the plane, Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures, 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, Outlier respecting points approximation, Diameter, width, closest line pair, and parametric searching, I/O-efficient path traversal in succinct planar graphs, Minimizing the sum of diameters efficiently, Tight bounds for connecting sites across barriers, An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains, Hausdorff approximation of 3D convex polytopes, 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, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, A general approach for cache-oblivious range reporting and approximate range counting, Computing the \(k\)-visibility region of a point in a polygon, A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions, Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra, Low complexity algorithms for optimal consumer push-pull partial covering in the plane, Implicitly representing arrangements of lines or segments, An incremental reconstruction method for dynamic planar point location, Point set stratification and Delaunay depth, Rotationally monotone polygons, Triangulating point sets in space, Storing the subdivision of a polyhedral surface, Reporting and counting segment intersections, Variable resolution triangulations, Voronoi diagrams with barriers and on polyhedra for minimal path planning, Clamshell casting, On separating two simple polygons by a single translation, Light edges in degree-constrained graphs, An approximate algorithm for computing multidimensional convex hulls, Semi-Lagrangian methods for level set equations, A parallel algorithm for constructing projection polyhedra, Linear time approximation of 3D convex polytopes, Efficient visibility queries in simple polygons, On rectilinear link distance, The power of geometric duality revisited, Finding extreme points in three dimensions and solving the post-office problem in the plane, Computing a median point of a simple rectilinear polygon, A workbench for computational geometry