Optimal Point Location in a Monotone Subdivision

DOI10.1137/0215023zbMath0602.68102DBLPjournals/siamcomp/EdelsbrunnerGS86OpenAlexW2132026455WikidataQ56288796 ScholiaQ56288796MaRDI QIDQ3738618

Jorge Stolfi, Leonidas J. Guibas, Herbert Edelsbrunner

Publication date: 1986

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

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

zbMATH Keywords

planar graphscomputational geometrygraph traversalmonotone polygonshit detectionlayered dag

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

Finding Pairwise Intersections Inside a Query Range ⋮ On condorcet and median points of simple rectilinear polygons ⋮ Input-sensitive compliant motion in the plane ⋮ Star unfolding of a polytope with applications ⋮ Single-Point Visibility Constraint Minimum Link Paths in Simple Polygons ⋮ Computing the smallest k-enclosing circle and related problems ⋮ Tetrahedrizing point sets in three dimensions ⋮ DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES ⋮ An algorithm for generalized point location and its applications ⋮ Adaptive Point Location in Planar Convex Subdivisions ⋮ AN IMPROVED ALGORITHM FOR SUBDIVISION TRAVERSAL WITHOUT EXTRA STORAGE ⋮ OPTIMAL PARALLEL PREPROCESSING ALGORITHMS FOR TESTING WEAK VISIBILITY OF POLYGONS FROM SEGMENTS ⋮ AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗ ⋮ New bounds for range closest-pair problems ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane ⋮ An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs ⋮ An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³ ⋮ Space-efficient functional offline-partially-persistent trees with applications to planar point location ⋮ Dynamic connectivity in disk graphs ⋮ Unnamed Item ⋮ Farthest-point Voronoi diagrams in the presence of rectangular obstacles ⋮ FAST CLUSTERING AND MINIMUM WEIGHT MATCHING ALGORITHMS FOR VERY LARGE MOBILE BACKBONE WIRELESS NETWORKS ⋮ Searching for the closest-pair in a query translate ⋮ Farthest-point queries with geometric and combinatorial constraints ⋮ An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model ⋮ A fast semi-Lagrangian contouring method for moving interfaces ⋮ Output-sensitive generation of the perspective view of isothetic parallelepipeds ⋮ Intersection queries in sets of disks ⋮ ON GEOMETRIC PATH QUERY PROBLEMS ⋮ A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING ⋮ INTERSECTION PROBLEMS ON SEGMENTS UNDER BOUNDARY UPDATES WITH APPLICATION TO PERSISTENT LISTS ⋮ PARETO ENVELOPES IN SIMPLE POLYGONS ⋮ Algorithms for subpath convex hull queries and ray-shooting among segments ⋮ On the line-separable unit-disk coverage and related problems ⋮ Unnamed Item ⋮ Faster goal-oriented shortest path search for bulk and incremental detailed routing ⋮ An optimal algorithm for roundness determination on convex polygons ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dynamic planar point location with optimal query time ⋮ External memory planar point location with logarithmic updates ⋮ Dynamic Trees and Dynamic Point Location ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ New Bounds for Range Closest-Pair Problems ⋮ Adaptive Planar Point Location ⋮ Abstract Voronoi Diagrams from Closed Bisecting Curves ⋮ Locating two obnoxious facilities using the weighted maximin criterion ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions ⋮ Query-Points Visibility Constraint Minimum Link Paths in Simple Polygons ⋮ Dog Bites Postman ⋮ An efficient \(k\) nearest neighbors searching algorithm for a query line. ⋮ Computing the smallest \(k\)-enclosing circle and related problems ⋮ Generalized Delaunay triangulation for planar graphs ⋮ Extremal polygon containment problems ⋮ Ray shooting in polygons using geodesic triangulations ⋮ Selecting distances in the plane ⋮ Computing the intersection-depth to polyhedra ⋮ I/O-efficient dynamic planar point location ⋮ Compressing spatio-temporal trajectories ⋮ Computing the optimal bridge between two convex polygons ⋮ Solving related two- and three-dimensional linear programming problems in logarithmic time ⋮ Fast domino tileability ⋮ Using geometry to solve the transportation problem in the plane ⋮ Rectilinear short path queries among rectangular obstacles ⋮ Geometric complexity of some location problems ⋮ Fractional cascading. I: A data structuring technique ⋮ Fractional cascading. II: Applications ⋮ A sweepline algorithm for Voronoi diagrams ⋮ Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons ⋮ A time-optimal parallel algorithm for three-dimensional convex hulls ⋮ A new algorithm for shortest paths among obstacles in the plane ⋮ Reverse shortest path problem in weighted unit-disk graphs ⋮ Shortest paths among transient obstacles ⋮ Optimal randomized incremental construction for guaranteed logarithmic planar point location ⋮ Rectilinear shortest paths in the presence of rectangular barriers ⋮ Optimal cooperative search in fractional cascaded data structures ⋮ A compact piecewise-linear Voronoi diagram for convex sites in the plane ⋮ The shortest watchtower and related problems for polyhedral terrains ⋮ Faster goal-oriented shortest path search for bulk and incremental detailed routing ⋮ Establishing order in planar subdivisions ⋮ A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency ⋮ (Approximate) uncertain skylines ⋮ An optimal algorithm for roundness determination on convex polygons ⋮ A multifacility location problem on median spaces ⋮ Topologically sweeping an arrangement ⋮ Shortest paths in the plane with obstacle violations ⋮ Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\) ⋮ Improved algorithms for the farthest colored Voronoi diagram of segments ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ Range queries on uncertain data ⋮ Reasoning about visibility ⋮ Farthest-polygon Voronoi diagrams ⋮ Reachable region query and its applications ⋮ Dynamic fractional cascading ⋮ Visibility and intersection problems in plane geometry ⋮ Computational geometry in a curved world ⋮ Dynamic maintenance of planar digraphs, with applications ⋮ Triangulating a nonconvex polytope ⋮ Dynamic planar point location with optimal query time

This page was built for publication: Optimal Point Location in a Monotone Subdivision