Visibility and intersection problems in plane geometry
From MaRDI portal
Publication:910213
DOI10.1007/BF02187747zbMath0695.68033MaRDI QIDQ910213
Bernard Chazelle, Leonidas J. Guibas
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131096
68Q25: Analysis of algorithms and problem complexity
68U99: Computing methodologies and applications
52A10: Convex sets in (2) dimensions (including convex curves)
52A30: Variants of convex sets (star-shaped, ((m, n))-convex, etc.)
Related Items
Determining Weak Visibility of a Polygon from an Edge in Parallel, ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS, OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS, Processing an Offline Insertion-Query Sequence with Applications, Polygons cuttable by a circular saw, Guarding a terrain by two watchtowers, Searching for mobile intruders in circular corridors by two 1-searchers, A note on the combinatorial structure of the visibility graph in simple polygons, Decomposing the boundary of a nonconvex polyhedron, LR-visibility in polygons, On the minimality of polygon triangulation, Storing line segments in partition trees, An optimal algorithm for the boundary of a cell in a union of rays, Some chain visibility problems in a simple polygon, An efficient algorithm for the three-guard problem, Fractional cascading. II: Applications, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Separating two simple polygons by a sequence of translations, Computing the link center of a simple polygon, An optimal visibility graph algorithm for triangulated simple polygons, Triangulating a simple polygon in linear time, Local minima for indefinite quadratic knapsack problems, Applications of a new space-partitioning technique, Special subgraphs of weighted visibility graphs, Parallel methods for visibility and shortest-path problems in simple polygons, The furthest-site geodesic Voronoi diagram, On the general motion-planning problem with two degrees of freedom, Implicitly representing arrangements of lines or segments, An improved technique for output-sensitive hidden surface removal, On range searching with semialgebraic sets, Efficient ray shooting and hidden surface removal, Ray shooting in polygons using geodesic triangulations, Distance measures on intersecting objects and their applications, Can visibility graphs be represented compactly?, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, Approximation algorithms for the watchman route and zookeeper's problems., Ray shooting and stone throwing with near-linear storage, Quasi-optimal range searching in spaces of finite VC-dimension, Efficient visibility queries in simple polygons, An O\((n\log n)\) algorithm for the zoo-keeper's problem, Characterizing and recognizing the visibility graph of a funnel-shaped polygon, A linear-time algorithm for constructing a circular visibility diagram, Computing depth orders for fat objects and related problems, Generalized hidden surface removal, A linear-time 2-approximation algorithm for the watchman route problem for simple polygons, Query point visibility computation in polygons with holes, A unified and efficient solution to the room search problem, Locating two obnoxious facilities using the weighted maximin criterion, An algorithm for generalized point location and its applications, PROCESSING AN OFFLINE INSERTION-QUERY SEQUENCE WITH APPLICATIONS, EXACT AND APPROXIMATION ALGORITHMS FOR FINDING AN OPTIMAL BRIDGE CONNECTING TWO SIMPLE POLYGONS, FINDING ALL DOOR LOCATIONS THAT MAKE A ROOM SEARCHABLE, Dynamic Trees and Dynamic Point Location
Cites Work
- Computing on a free tree via complexity-preserving mappings
- Fractional cascading. I: A data structuring technique
- Fractional cascading. II: Applications
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Optimal shortest path queries in a simple polygon
- Optimal Point Location in a Monotone Subdivision
- Filtering Search: A New Approach to Query-Answering
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- Design and implementation of an efficient priority queue