Location of a Point in a Planar Subdivision and Its Applications

DOI10.1137/0206043zbMath0357.68034OpenAlexW2004389974MaRDI QIDQ4133115

No author found.

Publication date: 1977

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

Full work available at URL: https://doi.org/10.1137/0206043

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items

Generalized Delaunay triangulation for planar graphs, Using geometry to solve the transportation problem in the plane, Fractional cascading. II: Applications, A time-optimal parallel algorithm for three-dimensional convex hulls, Adaptive Point Location in Planar Convex Subdivisions, Decomposition and intersection of simple splinegons, AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗, Optimal randomized incremental construction for guaranteed logarithmic planar point location, On decomposing polygons into uniformly monotone parts, Optimal cooperative search in fractional cascaded data structures, Establishing order in planar subdivisions, A fast algorithm for point-location in a finite element mesh, Voronoi diagrams from convex hulls, On Taxicab Distance Mean Functions and their Geometric Applications: Methods, Implementations and Examples, The design and analysis of a new hybrid sorting algorithm, A space-optimal solution of general region location, Dynamic maintenance of planar digraphs, with applications, Minimum k-partitioning of rectilinear polygons, Dynamic planar point location with optimal query time, Guarding curvilinear art galleries with vertex or point guards, Bounds for point recolouring in geometric graphs, Drawing a rooted tree as a rooted \(y\)-monotone minimum spanning tree, Query point visibility computation in polygons with holes, COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION, A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING, Triangulating a simple polygon, A note on the graph isomorphism counting problem, Finding the intersection of two convex polyhedra, An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains, Dynamic planar point location with optimal query time, Moving a disc between polygons, An incremental reconstruction method for dynamic planar point location, Storing the subdivision of a polyhedral surface, Affine invariant triangulations, Voronoi diagrams with barriers and on polyhedra for minimal path planning, Dynamic Trees and Dynamic Point Location, Complexity of projected images of convex subdivisions, Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model, Comparison of various trees for nearest-point search with/without the Voronoi diagram., Translating a convex polyhedron over monotone polyhedra, Efficient visibility queries in simple polygons, Visibility with a moving point of view