Ray shooting in polygons using geodesic triangulations
From MaRDI portal
Publication:1330785
DOI10.1007/BF01377183zbMATH Open0813.68158MaRDI QIDQ1330785FDOQ1330785
Authors: Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Michelangelo Grigni, John Hershberger, Micha Sharir, Jack Snoeyink 
Publication date: 10 August 1994
Published in: Algorithmica (Search for Journal in Brave)
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Title not available (Why is that?)
- Triangulating a simple polygon in linear time
- Optimal Search in Planar Subdivisions
- The complexity of cutting complexes
- Maintenance of configurations in the plane
- Title not available (Why is that?)
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Fast Algorithms for Finding Nearest Common Ancestors
- Optimal Point Location in a Monotone Subdivision
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Visibility and intersection problems in plane geometry
- Euclidean shortest paths in the presence of rectilinear barriers
- Optimal shortest path queries in a simple polygon
- Fractional cascading. I: A data structuring technique
- Fractional cascading. II: Applications
- A linear algorithm for computing the visibility polygon from a point
- COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS
- Fast detection of polyhedral intersection
- A new data structure for shortest path queries in a simple polygon
Cited In (76)
- Global Curve Simplification
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
- Faster algorithms for growing prioritized disks and rectangles
- Kinetic collision detection with fast flight plan changes
- On ray shooting in convex polytopes
- AN ALGORITHM FOR SEARCHING A POLYGONAL REGION WITH A FLASHLIGHT
- Ray shooting and stone throwing with near-linear storage
- Partially walking a polygon
- Minimum-link paths revisited
- Binary plane partitions for disjoint line segments
- Minimum weight convex Steiner partitions
- Peeling potatoes near-optimally in near-linear time
- Hierarchical decompositions and circular ray shooting in simple polygons
- Algorithmic enumeration of surrounding polygons
- KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS
- Computing \(L_1\) shortest paths among polygonal obstacles in the plane
- Visibility and ray shooting queries in polygonal domains
- A polynomial-time algorithm for computing the resilience of arrangements of ray sensors
- Weak visibility queries of line segments in simple polygons
- Lower bounds for intersection searching and fractional cascading in higher dimension
- Computing depth orders for fat objects and related problems
- Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
- Voronoi diagrams for a moderate-sized point-set in a simple polygon
- Combinatorial pseudo-triangulations
- k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
- Title not available (Why is that?)
- TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS
- Pointed binary encompassing trees: simple and optimal
- Largest triangle inside a terrain
- Stabbing circles for sets of segments in the plane
- Quickest visibility queries in polygonal domains
- Routing in a polygonal terrain with the shortest beacon watchtower
- Linear data structures for fast ray-shooting amidst convex polyhedra
- Title not available (Why is that?)
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Multi cover of a polygon minimizing the sum of areas
- Multi cover of a polygon minimizing the sum of areas
- Adaptive planar point location
- 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
- Minimum weight pseudo-triangulations
- On \(k\)-convex polygons
- A faster algorithm for computing motorcycle graphs
- Relative convex hulls in semi-dynamic arrangements
- A kinetic triangulation scheme for moving points in the plane
- Self-approaching paths in simple polygons
- Visibility and Ray Shooting Queries in Polygonal Domains
- Tight degree bounds for pseudo-triangulations of points
- Minimum Cell Connection in Line Segment Arrangements
- On the number of pseudo-triangulations of certain point sets
- Computing a geodesic two-center of points in a simple polygon
- A near-optimal algorithm for shortest paths among curved obstacles in the plane
- The stochastic walk algorithms for point location in pseudo-triangulations
- Convexity minimizes pseudo-triangulations
- Kinetic collision detection between two simple polygons.
- ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
- Linear transformation distance for bichromatic matchings
- Decomposing a simple polygon into pseudo-triangles and convex polygons
- An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
- A vertex-face assignment for plane graphs
- Polygons cuttable by a circular saw
- Geodesic disks and clustering in a simple polygon
- Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number
- Title not available (Why is that?)
- Algorithms for Computing Diffuse Reflection Paths in Polygons
- The geodesic farthest-point Voronoi diagram in a simple polygon
- Partially Walking a Polygon
- New sequential and parallel algorithms for computing the \(\beta\)-spectrum
- COMPUTATIONAL GEOMETRY COLUMN 43
- How to cut corners and get bounded convex curvature
- Algorithms for subpath convex hull queries and ray-shooting among segments
- Uniformly monotone partitioning of polygons
- On Voronoi visibility maps of 1.5D terrains with multiple viewpoints
- An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction
- k-pairs non-crossing shortest paths in a simple polygon
- Resolving Loads with Positive Interior Stresses
- Finding the shortest boundary guard of a simple polygon
This page was built for publication: Ray shooting in polygons using geodesic triangulations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1330785)
