Ray shooting in polygons using geodesic triangulations
From MaRDI portal
Publication:1330785
DOI10.1007/BF01377183zbMath0813.68158MaRDI QIDQ1330785
Leonidas J. Guibas, Bernard Chazelle, Herbert Edelsbrunner, Jack Scott Snoeyink, J. E. Hershberger, Micha Sharir, Michelangelo Grigni
Publication date: 10 August 1994
Published in: Algorithmica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Tight degree bounds for pseudo-triangulations of points ⋮ Kinetic collision detection with fast flight plan changes ⋮ Lower bounds for intersection searching and fractional cascading in higher dimension ⋮ Resolving Loads with Positive Interior Stresses ⋮ Minimum weight pseudo-triangulations ⋮ KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS ⋮ AN ALGORITHM FOR SEARCHING A POLYGONAL REGION WITH A FLASHLIGHT ⋮ ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS ⋮ COMPUTATIONAL GEOMETRY COLUMN 43 ⋮ Combinatorial pseudo-triangulations ⋮ 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects ⋮ Computing depth orders for fat objects and related problems ⋮ Convexity minimizes pseudo-triangulations ⋮ Self-approaching paths in simple polygons ⋮ Peeling Potatoes Near-Optimally in Near-Linear Time ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane ⋮ How to cut corners and get bounded convex curvature ⋮ On Voronoi visibility maps of 1.5D terrains with multiple viewpoints ⋮ An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons ⋮ Routing in a polygonal terrain with the shortest beacon watchtower ⋮ Linear transformation distance for bichromatic matchings ⋮ On \(k\)-convex polygons ⋮ A kinetic triangulation scheme for moving points in the plane ⋮ The stochastic walk algorithms for point location in pseudo-triangulations ⋮ Kinetic collision detection between two simple polygons. ⋮ Minimum-link paths revisited ⋮ Largest triangle inside a terrain ⋮ A faster algorithm for computing motorcycle graphs ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ Decomposing a simple polygon into pseudo-triangles and convex polygons ⋮ Decompositions, partitions, and coverings with convex polygons and pseudo-triangles ⋮ Algorithmic enumeration of surrounding polygons ⋮ Stabbing circles for sets of segments in the plane ⋮ GEODESIC DISKS AND CLUSTERING IN A SIMPLE POLYGON ⋮ MULTI COVER OF A POLYGON MINIMIZING THE SUM OF AREAS ⋮ On the number of pseudo-triangulations of certain point sets ⋮ Binary plane partitions for disjoint line segments ⋮ Visibility and ray shooting queries in polygonal domains ⋮ Minimum weight convex Steiner partitions ⋮ Finding the shortest boundary guard of a simple polygon ⋮ Ray shooting and stone throwing with near-linear storage ⋮ k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON ⋮ Polygons cuttable by a circular saw ⋮ Algorithms for Computing Diffuse Reflection Paths in Polygons ⋮ Pointed binary encompassing trees: simple and optimal ⋮ Voronoi diagrams for a moderate-sized point-set in a simple polygon ⋮ Global Curve Simplification ⋮ Multi Cover of a Polygon Minimizing the Sum of Areas ⋮ Partially Walking a Polygon ⋮ The geodesic farthest-point Voronoi diagram in a simple polygon ⋮ A vertex-face assignment for plane graphs ⋮ Quickest visibility queries in polygonal domains ⋮ Faster algorithms for growing prioritized disks and rectangles ⋮ A POLYNOMIAL-TIME ALGORITHM FOR COMPUTING THE RESILIENCE OF ARRANGEMENTS OF RAY SENSORS ⋮ Computing a geodesic two-center of points in a simple polygon ⋮ Partially walking a polygon ⋮ Adaptive Planar Point Location ⋮ Minimum Cell Connection in Line Segment Arrangements ⋮ TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS ⋮ New sequential and parallel algorithms for computing the \(\beta\)-spectrum ⋮ Weak visibility queries of line segments in simple polygons ⋮ An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction
Cites Work
- Unnamed Item
- Unnamed Item
- Fast detection of polyhedral intersection
- Visibility and intersection problems in plane geometry
- Fractional cascading. I: A data structuring technique
- Fractional cascading. II: Applications
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- The complexity of cutting complexes
- Maintenance of configurations in the plane
- Triangulating a simple polygon in linear time
- A new data structure for shortest path queries in a simple polygon
- Optimal shortest path queries in a simple polygon
- COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS
- Fast Algorithms for Finding Nearest Common Ancestors
- Euclidean shortest paths in the presence of rectilinear barriers
- Optimal Point Location in a Monotone Subdivision
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- A linear algorithm for computing the visibility polygon from a point
- Optimal Search in Planar Subdivisions
