Visibility of disjoint polygons

DOI10.1007/BF01840436zbMath0611.68062MaRDI QIDQ1087340

Hiroshi Imai, Tetsuo Asano, Takao Asano, Leonidas J. Guibas, J. E. Hershberger

Publication date: 1986

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

shortest pathcomputer graphicsroboticscomputational geometryvisibility graphdata structurevisibility polygonhidden-line elimination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Related Items

Generalized Delaunay triangulation for planar graphs, The visibility diagram: A data structure for visibility problems and motion planning, Characterizing and recognizing the visibility graph of a funnel-shaped polygon, A tight lower bound on the size of visibility graphs, Routing among convex polygonal obstacles in the plane, A new algorithm for shortest paths among obstacles in the plane, On multiple moving objects, Shortest paths among transient obstacles, Shortest path between two simple polygons, Rectilinear shortest paths in the presence of rectangular barriers, An optimal visibility graph algorithm for triangulated simple polygons, An algorithmic approach to some problems in terrain navigation, Space–Query-Time Tradeoff for Computing the Visibility Polygon, Routing in polygonal domains, Minimal tangent visibility graphs, Shortest paths in the plane with obstacle violations, On rainbow quadrilaterals in colored point sets, Incremental Algorithms to Update Visibility Polygons, The complexity of planar compliant motion planning under uncertainty, On maximum flows in polyhedral domains, Visibility graphs and obstacle-avoiding shortest paths, On graphs preserving rectilinear shortest paths in the presence of obstacles, Dynamic Algorithms for Visibility Polygons in Simple Polygons, \(L_ 1\) shortest paths among polygonal obstacles in the plane, Perfect binary space partitions, Hidden surface removal for \(c\)-oriented polyhedra, An efficient algorithm for one-step planar compliant motion planning with uncertainty, Computing the visibility polygon of an island in a polygonal domain, Computing the full visibility graph of a set of line segments, Upper envelope onion peeling, Approximation algorithms for art gallery problems in polygons, Visibility and ray shooting queries in polygonal domains, A linear time algorithm to remove winding of a simple polygon, Upper envelope onion peeling, Finding the upper envelope of n line segments in O(n log n) time, An exact geometry-based algorithm for path planning, Unnamed Item, Planning a time-minimal motion among moving obstacles, A fast algorithm for computing sparse visibility graphs, Topologically sweeping visibility complexes via pseudotriangulations, Rectilinear paths among rectilinear obstacles, Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane, VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME, Using Gale transforms in computational geometry, Efficient visibility queries in simple polygons, Routing in Polygonal Domains, A Computational Geometric Approach to Visual Hulls

Cites Work

• 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
• The power of geometric duality
• Triangulating a simple polygon
• Visibility of a simple polygon
• Euclidean shortest paths in the presence of rectilinear barriers
• Constructing Arrangements of Lines and Hyperplanes with Applications
• A linear algorithm for computing the visibility polygon from a point