Visibility and intersection problems in plane geometry

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

zbMATH Keywords

computational geometry; intersection problems; visibility problems

Mathematics Subject Classification ID

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, 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, 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