Visibility and intersection problems in plane geometry
From MaRDI portal
Within the field of visibility and intersection problems, the authors are focussing on the following problem: ``Given a simple polygon P and a pair (q,u) consisting of a point q and a direction u, imagine that we follow the path of a straight-line ray r from q in the direction u. We wish to know the first intersection (if any) of r with the boundary of P... In posing this question we assume that P is fixed once and for all, so we are allowed to do preprocessing on it. New data structures are proposed for solving this problem in O(log n)-time with preprocessing which takes time O(n log n) and space O(n).
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
Cites work
- An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
- Computing on a free tree via complexity-preserving mappings
- Design and implementation of an efficient priority queue
- Filtering Search: A New Approach to Query-Answering
- 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 Point Location in a Monotone Subdivision
- Optimal shortest path queries in a simple polygon
Cited in
(92)- 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.
- Computing simple paths from given points inside a polygon
- Ray shooting and stone throwing with near-linear storage
- A unifying approach for a class of problems in the computational geometry of polygons
- 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
- Algorithmic enumeration of surrounding polygons
- Computing optimal shortcuts for networks
- Line segment visibility with sidedness constraints
- Visibility and ray shooting queries in polygonal domains
- Shortcut sets for the locus of plane Euclidean networks
- Weak visibility counting in simple polygons
- A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
- Computing \(L_1\) shortest paths among polygonal obstacles in the plane
- Approximation algorithms for decomposing octilinear polygons
- Optimum sweeps of simple polygons with two guards
- Minimization of the maximum distance between the two guards patrolling a polygonal region
- 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
- Maintaining visibility of a polygon with a moving point of view
- Incremental algorithms to update visibility polygons
- Efficient algorithms for touring a sequence of convex polygons and related problems
- 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
- Determining Weak Visibility of a Polygon from an Edge in Parallel
- Simplex Range Searching and Its Variants: A Review
- ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
- OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
- Graphics in flatland revisited
- The visibility diagram: A data structure for visibility problems and motion planning
- Upper envelope onion peeling
- Intersection queries in sets of disks
- Decomposing the boundary of a nonconvex polyhedron
- Computing depth orders and related problems
- Computing common tangents without a separating line
- Shortcut sets for plane Euclidean networks (extended abstract)
- An optimal algorithm to compute the inverse beacon attraction region
- Computing the visibility polygon of an island in a polygonal domain
- Dynamic algorithms for visibility polygons in simple polygons
- scientific article; zbMATH DE number 5490684 (Why is no real title available?)
- Processing an Offline Insertion-Query Sequence with Applications
- Tracing compressed curves in triangulated surfaces
- Polygons cuttable by a circular saw
- Guarding a terrain by two watchtowers
- Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles
- Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
- Searching for mobile intruders in circular corridors by two 1-searchers
- Algorithms for subpath convex hull queries and ray-shooting among segments
- A note on the combinatorial structure of the visibility graph in simple polygons
- Decomposing the boundary of a nonconvex polyhedron
- LR-visibility in polygons
- The geodesic edge center of a simple polygon
- Algorithms for halfplane coverage and related problems
- Computing instance-optimal kernels in two dimensions
- Algorithms for halfplane coverage and related problems
- Compact representation of semilinear and terrain-like graphs
- On the minimality of polygon triangulation
- Near optimal line segment queries in simple 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
- Non-Euclidean visibility problems
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)
