Optimal Point Location in a Monotone Subdivision
From MaRDI portal
Publication:3738618
DOI10.1137/0215023zbMath0602.68102OpenAlexW2132026455WikidataQ56288796 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies and applications (68U99)
Related Items
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, Spanning trees crossing few barriers, Partitioning arrangements of lines. II: Applications, Near-optimal algorithms for shortest paths in weighted unit-disk graphs, Euclidean minimum spanning trees and bichromatic closest pairs, Triangulating a simple polygon in linear time, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Randomized incremental construction of Delaunay and Voronoi diagrams, Searching for segments with largest relative overlap, Optimal randomized parallel algorithms for computational geometry, 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, Output-sensitive generation of the perspective view of isothetic parallelepipeds, Intersection queries in sets of disks, Diameter, width, closest line pair, and parametric searching, Minimizing the sum of diameters efficiently, Tight bounds for connecting sites across barriers, Approximate motion planning and the complexity of the boundary of the union of simple geometric figures, Minimum-link paths among obstacles in the plane, Finding pairwise intersections inside a query range, Data structures for halfplane proximity queries and incremental Voronoi diagrams, An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains, An optimal-time algorithm for shortest paths on a convex polytope in three dimensions, Fast computation of smallest enclosing circle with center on a query line segment, \(L_{1}\) shortest path queries in simple polygons, Linear space data structures for two types of range search, The complexity and construction of many faces in arrangements of lines and of segments, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, An exact geometry-based algorithm for path planning, A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon, Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra, Testing the necklace condition for shortest tours and optimal factors in the plane, Implicitly representing arrangements of lines or segments, Moving a disc between polygons, An incremental reconstruction method for dynamic planar point location, Locating a robot with angle measurements, A near-linear algorithm for the planar segment-center problem, A dual approach to detect polyhedral intersections in arbitrary dimensions, Storing the subdivision of a polyhedral surface, Optimal shortest path queries in a simple polygon, Quickest visibility queries in polygonal domains, Fast tree-based redistancing for level set computations, Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model, Algorithms for bichromatic line-segment problems and polyhedral terrains, Weak visibility queries of line segments 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, 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 ℝ3, 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, Unnamed Item, 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
