Visibility and intersection problems in plane geometry

DOI10.1007/BF02187747zbMath0695.68033OpenAlexW2088617781MaRDI 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 geometryintersection problemsvisibility problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Convex sets in (2) dimensions (including convex curves) (52A10) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30)

Related Items (83)

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? ⋮ Maintaining visibility of a polygon with a moving point of view ⋮ Computing simple paths from given points inside a polygon ⋮ PROCESSING AN OFFLINE INSERTION-QUERY SEQUENCE WITH APPLICATIONS ⋮ Graphics in flatland revisited ⋮ The visibility diagram: A data structure for visibility problems and motion planning ⋮ Computing depth orders and related problems ⋮ Characterizing and recognizing the visibility graph of a funnel-shaped polygon ⋮ Computing common tangents without a separating line ⋮ A linear-time algorithm for constructing a circular visibility diagram ⋮ A linear-time 2-approximation algorithm for the watchman route problem for simple polygons ⋮ Fractional cascading. II: Applications ⋮ Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons ⋮ An algorithm for generalized point location and its applications ⋮ Separating two simple polygons by a sequence of translations ⋮ Computing the link center of a simple polygon ⋮ ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS ⋮ OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS ⋮ An optimal visibility graph algorithm for triangulated simple polygons ⋮ 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects ⋮ Processing an Offline Insertion-Query Sequence with Applications ⋮ Computing depth orders for fat objects and related problems ⋮ Generalized hidden surface removal ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ Near optimal line segment queries in simple polygons ⋮ Approximation algorithms for decomposing octilinear polygons ⋮ Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Incremental Algorithms to Update Visibility Polygons ⋮ 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 ⋮ Searching for mobile intruders in circular corridors by two 1-searchers ⋮ Optimum sweeps of simple polygons with two guards ⋮ Minimization of the maximum distance between the two guards patrolling a polygonal region ⋮ Approximation algorithms for the watchman route and zookeeper's problems. ⋮ Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems ⋮ Triangulating a simple polygon in linear time ⋮ Dynamic Algorithms for Visibility Polygons in Simple Polygons ⋮ Query point visibility computation in polygons with holes ⋮ Local minima for indefinite quadratic knapsack problems ⋮ A note on the combinatorial structure of the visibility graph in simple polygons ⋮ Algorithmic enumeration of surrounding polygons ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ LR-visibility in polygons ⋮ FINDING ALL DOOR LOCATIONS THAT MAKE A ROOM SEARCHABLE ⋮ Shortcut sets for plane Euclidean networks (extended abstract) ⋮ Computing the visibility polygon of an island in a polygonal domain ⋮ Applications of a new space-partitioning technique ⋮ Special subgraphs of weighted visibility graphs ⋮ Parallel methods for visibility and shortest-path problems in simple polygons ⋮ A unified and efficient solution to the room search problem ⋮ Computing optimal shortcuts for networks ⋮ The furthest-site geodesic Voronoi diagram ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ Visibility and ray shooting queries in polygonal domains ⋮ Ray shooting and stone throwing with near-linear storage ⋮ Intersection queries in sets of disks ⋮ Upper envelope onion peeling ⋮ Polygons cuttable by a circular saw ⋮ Guarding a terrain by two watchtowers ⋮ An efficient algorithm for the three-guard problem ⋮ EXACT AND APPROXIMATION ALGORITHMS FOR FINDING AN OPTIMAL BRIDGE CONNECTING TWO SIMPLE POLYGONS ⋮ On the general motion-planning problem with two degrees of freedom ⋮ Implicitly representing arrangements of lines or segments ⋮ Tracing compressed curves in triangulated surfaces ⋮ On the minimality of polygon triangulation ⋮ Quasi-optimal range searching in spaces of finite VC-dimension ⋮ Dynamic Trees and Dynamic Point Location ⋮ An optimal algorithm to compute the inverse beacon attraction region ⋮ Shortcut sets for the locus of plane Euclidean networks ⋮ Locating two obnoxious facilities using the weighted maximin criterion ⋮ Efficient visibility queries in simple polygons ⋮ Weak visibility queries of line segments in simple polygons ⋮ Weak visibility counting in simple polygons ⋮ Determining Weak Visibility of a Polygon from an Edge in Parallel ⋮ An improved technique for output-sensitive hidden surface removal ⋮ An O\((n\log n)\) algorithm for the zoo-keeper's problem

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

This page was built for publication: Visibility and intersection problems in plane geometry