Visibility of disjoint polygons
From MaRDI portal
Publication:1087340
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)
shortest path; computer graphics; robotics; computational geometry; visibility graph; data structure; visibility polygon; hidden-line elimination
68Q25: Analysis of algorithms and problem complexity
68U99: Computing methodologies and applications
51M20: Polyhedra and polytopes; regular figures, division of spaces
Related Items
A Computational Geometric Approach to Visual Hulls, VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME, Upper envelope onion peeling, Unnamed Item, The visibility diagram: A data structure for visibility problems and motion planning, Dynamic Algorithms for Visibility Polygons in Simple Polygons, Routing in Polygonal Domains, Space–Query-Time Tradeoff for Computing the Visibility Polygon, Computing the visibility polygon of an island in a polygonal domain, Finding the upper envelope of n line segments in O(n log n) time, Perfect binary space partitions, Using Gale transforms in computational geometry, The complexity of planar compliant motion planning under uncertainty, On maximum flows in polyhedral domains, Approximation algorithms for art gallery problems in polygons, Generalized Delaunay triangulation for planar graphs, A tight lower bound on the size of visibility graphs, On multiple moving objects, 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, On graphs preserving rectilinear shortest paths in the presence of obstacles, \(L_ 1\) shortest paths among polygonal obstacles in the plane, Hidden surface removal for \(c\)-oriented polyhedra, An efficient algorithm for one-step planar compliant motion planning with uncertainty, Computing the full visibility graph of a set of line segments, Upper envelope onion peeling, Planning a time-minimal motion among moving obstacles, A fast algorithm for computing sparse visibility graphs, A new algorithm for shortest paths among obstacles in the plane, An exact geometry-based algorithm for path planning, Topologically sweeping visibility complexes via pseudotriangulations, Efficient visibility queries in simple polygons, Characterizing and recognizing the visibility graph of a funnel-shaped polygon, Minimal tangent visibility graphs, Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane, Routing among convex polygonal obstacles in the plane, Shortest paths among transient obstacles, Routing in polygonal domains, Shortest paths in the plane with obstacle violations, Visibility and ray shooting queries in polygonal domains, A linear time algorithm to remove winding of a simple polygon, Rectilinear paths among rectilinear obstacles, On rainbow quadrilaterals in colored point sets, Incremental Algorithms to Update Visibility Polygons, Visibility graphs and obstacle-avoiding shortest paths
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
