Ray shooting in polygons using geodesic triangulations (Q1330785): Difference between revisions

This paper presents a new kind of triangulation of simple polygons, which has a low stabbing number (any segment inside the polygon crosses only a logarithmic number of `triangles') and which helps solve diverse visibility problems such as, ray shooting from inside or outside the polygon, visibility inside the polygon from a given point.

0 references

zbMATH Keywords

ray shooting

0 references

triangulation

0 references

simple polygons

0 references

visibility

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Triangulating a simple polygon in linear time

0 references

The complexity of cutting complexes

0 references

Fractional cascading. I: A data structuring technique

0 references

Fractional cascading. II: Applications

0 references

Visibility and intersection problems in plane geometry

0 references

Fast detection of polyhedral intersection

0 references

Optimal Point Location in a Monotone Subdivision

0 references

A linear algorithm for computing the visibility polygon from a point

0 references

Optimal shortest path queries in a simple polygon

0 references

Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons

0 references

COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS

0 references

Fast Algorithms for Finding Nearest Common Ancestors

0 references

A new data structure for shortest path queries in a simple polygon

0 references

Optimal Search in Planar Subdivisions

0 references

Euclidean shortest paths in the presence of rectilinear barriers

0 references

Q3219751

0 references

Maintenance of configurations in the plane

0 references

Q3694703

0 references

On Finding Lowest Common Ancestors: Simplification and Parallelization

0 references

Identifiers

zbMATH Open document ID

0813.68158

0 references

DOI

10.1007/BF01377183

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1330785

@@ Property / author @@
-Michelangelo Grigni
@@ Property / author: Michelangelo Grigni / rank @@
-Normal rank
@@ Property / author @@
-J. E. Hershberger
@@ Property / author: J. E. Hershberger / rank @@
-Normal rank
@@ Property / author @@
-Micha Sharir
@@ Property / author: Micha Sharir / rank @@
-Normal rank
@@ Property / author @@
-Jack Scott Snoeyink
@@ Property / author: Jack Scott Snoeyink / rank @@
-Normal rank
@@ Property / author @@
+Michelangelo Grigni
@@ Property / author: Michelangelo Grigni / rank @@
+Normal rank
@@ Property / author @@
+J. E. Hershberger
@@ Property / author: J. E. Hershberger / rank @@
+Normal rank
@@ Property / author @@
+Micha Sharir
@@ Property / author: Micha Sharir / rank @@
+Normal rank
@@ Property / author @@
+Jack Scott Snoeyink
@@ Property / author: Jack Scott Snoeyink / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Triangulating a simple polygon in linear time
@@ Property / cites work: Triangulating a simple polygon in linear time / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of cutting complexes
@@ Property / cites work: The complexity of cutting complexes / rank @@
+Normal rank
@@ Property / cites work @@
+Fractional cascading. I: A data structuring technique
+Normal rank
@@ Property / cites work @@
+Fractional cascading. II: Applications
@@ Property / cites work: Fractional cascading. II: Applications / rank @@
+Normal rank
@@ Property / cites work @@
+Visibility and intersection problems in plane geometry
+Normal rank
@@ Property / cites work @@
+Fast detection of polyhedral intersection
@@ Property / cites work: Fast detection of polyhedral intersection / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Point Location in a Monotone Subdivision
@@ Property / cites work: Optimal Point Location in a Monotone Subdivision / rank @@
+Normal rank
@@ Property / cites work @@
+A linear algorithm for computing the visibility polygon from a point
+Normal rank
@@ Property / cites work @@
+Optimal shortest path queries in a simple polygon
@@ Property / cites work: Optimal shortest path queries in a simple polygon / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
+Normal rank
@@ Property / cites work @@
+COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS
+Normal rank
@@ Property / cites work @@
+Fast Algorithms for Finding Nearest Common Ancestors
+Normal rank
@@ Property / cites work @@
+A new data structure for shortest path queries in a simple polygon
+Normal rank
@@ Property / cites work @@
+Optimal Search in Planar Subdivisions
@@ Property / cites work: Optimal Search in Planar Subdivisions / rank @@
+Normal rank
@@ Property / cites work @@
+Euclidean shortest paths in the presence of rectilinear barriers
+Normal rank
@@ Property / cites work @@
+Q3219751
@@ Property / cites work: Q3219751 / rank @@
+Normal rank
@@ Property / cites work @@
+Maintenance of configurations in the plane
@@ Property / cites work: Maintenance of configurations in the plane / rank @@
+Normal rank
@@ Property / cites work @@
+Q3694703
@@ Property / cites work: Q3694703 / rank @@
+Normal rank
@@ Property / cites work @@
+On Finding Lowest Common Ancestors: Simplification and Parallelization
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1330785