Visibility and intersection problems in plane geometry
From MaRDI portal
Publication:910213
DOI10.1007/BF02187747zbMATH Open0695.68033OpenAlexW2088617781MaRDI QIDQ910213FDOQ910213
Authors: Bernard Chazelle, Leonidas Guibas 
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131096
Recommendations
- Non-Euclidean visibility problems
- scientific article; zbMATH DE number 5542506
- Visibility graphs of point sets in the plane
- Visibility graphs of point sets in the plane
- scientific article; zbMATH DE number 16594
- scientific article; zbMATH DE number 4078149
- Visibility Algorithms in the Plane
- Visibility in semi-convex spaces
- Computing the visibility polygon from a convex set and related problems
- scientific article; zbMATH DE number 2087475
Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30)
Cites Work
- Filtering Search: A New Approach to Query-Answering
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Optimal Point Location in a Monotone Subdivision
- Design and implementation of an efficient priority queue
- Optimal shortest path queries in a simple polygon
- Fractional cascading. I: A data structuring technique
- Computing on a free tree via complexity-preserving mappings
- Fractional cascading. II: Applications
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
Cited In (87)
- An improved technique for output-sensitive hidden surface removal
- The furthest-site geodesic Voronoi diagram
- Dynamic Trees and Dynamic Point Location
- Locating two obnoxious facilities using the weighted maximin criterion
- Efficient visibility queries in simple polygons
- An algorithm for generalized point location and its applications
- The visibility diagram: A data structure for visibility problems and motion planning
- Storing line segments in partition trees
- Ray shooting and stone throwing with near-linear storage
- Title not available (Why is that?)
- Approximation algorithms for decomposing octilinear polygons
- A unified and efficient solution to the room search problem
- Parallel methods for visibility and shortest-path problems in simple polygons
- Decomposing the boundary of a nonconvex polyhedron
- Efficient ray shooting and hidden surface removal
- Query point visibility computation in polygons with holes
- Algorithmic enumeration of surrounding polygons
- Characterizing and recognizing the visibility graph of a funnel-shaped polygon
- Computing \(L_1\) shortest paths among polygonal obstacles in the plane
- Visibility and ray shooting queries in polygonal domains
- OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
- Computing depth orders for fat objects and related problems
- Maintaining visibility of a polygon with a moving point of view
- Applications of a new space-partitioning technique
- Implicitly representing arrangements of lines or segments
- On range searching with semialgebraic sets
- An efficient algorithm for the three-guard problem
- A unifying approach for a class of problems in the computational geometry of polygons
- Triangulating a simple polygon in linear time
- An O\((n\log n)\) algorithm for the zoo-keeper's problem
- Ray shooting in polygons using geodesic triangulations
- Computing the link center of a simple polygon
- Separating two simple polygons by a sequence of translations
- Quasi-optimal range searching in spaces of finite VC-dimension
- On the general motion-planning problem with two degrees of freedom
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Can visibility graphs be represented compactly?
- Computing depth orders and related problems
- 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
- Upper envelope onion peeling
- Near optimal line segment queries in simple polygons
- On the minimality of polygon triangulation
- Local minima for indefinite quadratic knapsack problems
- Distance measures on intersecting objects and their applications
- Efficient algorithms for touring a sequence of convex polygons and related problems
- An optimal algorithm for the boundary of a cell in a union of rays
- Some chain visibility problems in a simple polygon
- Approximation algorithms for the watchman route and zookeeper's problems.
- Non-Euclidean visibility problems
- Searching for mobile intruders in circular corridors by two 1-searchers
- Special subgraphs of weighted visibility graphs
- Intersection queries in sets of disks
- A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
- An optimal visibility graph algorithm for triangulated simple polygons
- Simplex Range Searching and Its Variants: A Review
- ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
- Shortcut sets for plane Euclidean networks (extended abstract)
- Computing the visibility polygon of an island in a polygonal domain
- Fractional cascading. II: Applications
- Polygons cuttable by a circular saw
- Dynamic algorithms for visibility polygons in simple polygons
- A note on the combinatorial structure of the visibility graph in simple polygons
- Decomposing the boundary of a nonconvex polyhedron
- LR-visibility in polygons
- Optimum sweeps of simple polygons with two guards
- Minimization of the maximum distance between the two guards patrolling a polygonal region
- Determining Weak Visibility of a Polygon from an Edge in Parallel
- Computing common tangents without a separating line
- Computing optimal shortcuts for networks
- Tracing compressed curves in triangulated surfaces
- Shortcut sets for the locus of plane Euclidean networks
- Computing simple paths from given points inside a polygon
- Finding all door locations that make a room searchable
- Algorithms for subpath convex hull queries and ray-shooting among segments
- Weak visibility counting in simple polygons
- An optimal algorithm to compute the inverse beacon attraction region
- Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles
- Processing an offline insertion-query sequence with applications
- Line segment visibility with sidedness constraints
- Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
- Graphics in flatland revisited
- Generalized hidden surface removal
- Guarding a terrain by two watchtowers
- EXACT AND APPROXIMATION ALGORITHMS FOR FINDING AN OPTIMAL BRIDGE CONNECTING TWO SIMPLE POLYGONS
- Processing an Offline Insertion-Query Sequence with Applications
- Incremental algorithms to update visibility polygons
- A linear-time algorithm for constructing a circular visibility diagram
This page was built for publication: Visibility and intersection problems in plane geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q910213)
