Topologically sweeping visibility complexes via pseudotriangulations

DOI10.1007/BF02712876zbMath0857.68063OpenAlexW2147097381MaRDI QIDQ1816465

Michel Pocchiola, Gert Vegter

Publication date: 26 November 1996

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02712876

zbMATH Keywords

visibility complexvisibility graphsfree bitangents

Mathematics Subject Classification ID

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 ⋮ LOCATING AN OBNOXIOUS LINE AMONG PLANAR OBJECTS ⋮ On planar path transformation ⋮ Minimum weight pseudo-triangulations ⋮ SIMULTANEOUS EDGE FLIPPING IN TRIANGULATIONS ⋮ Transforming pseudo-triangulations ⋮ Combinatorial pseudo-triangulations ⋮ Convexity minimizes pseudo-triangulations ⋮ Minimal tangent visibility graphs ⋮ Alternating paths along axis-parallel segments ⋮ On geometric path query problems ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane ⋮ Segment endpoint visibility graphs are Hamiltonian ⋮ The brick polytope of a sorting network ⋮ Celebrating Loday's associahedron ⋮ The stochastic walk algorithms for point location in pseudo-triangulations ⋮ Multitriangulations, pseudotriangulations and primitive sorting networks ⋮ Kinetic collision detection between two simple polygons. ⋮ ON THE EXPECTED SIZE OF THE 2D VISIBILITY COMPLEX ⋮ Decomposing a simple polygon into pseudo-triangles and convex polygons ⋮ Spiderman graph: visibility in urban regions ⋮ Decompositions, partitions, and coverings with convex polygons and pseudo-triangles ⋮ Pre-triangulations and liftable complexes ⋮ On the number of pseudo-triangulations of certain point sets ⋮ Visibility and ray shooting queries in polygonal domains ⋮ Planar minimally rigid graphs and pseudo-triangulations ⋮ Enumerating pseudo-triangulations in the plane ⋮ Computing pseudotriangulations via branched coverings ⋮ Pointed binary encompassing trees: simple and optimal ⋮ Empty pseudo-triangles in point sets ⋮ Quickest visibility queries in polygonal domains ⋮ Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane ⋮ Brick polytopes of spherical subword complexes and generalized associahedra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Greedoids
• A linear-time algorithm for a special case of disjoint set union
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Visibility of disjoint polygons
• Time and space efficient algorithms for shortest paths between convex polygons
• An optimal visibility graph algorithm for triangulated simple polygons
• Topologically sweeping an arrangement
• A fast algorithm for computing sparse visibility graphs
• Can visibility graphs be represented compactly?
• Minimal tangent visibility graphs
• DISTANCE VISIBILITY GRAPHS
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• An optimal algorithm for intersecting line segments in the plane
• Sorting jordan sequences in linear time using level-linked search trees
• COMPUTATIONAL GEOMETRY COLUMN 18