Visibility of disjoint polygons
type: Item
instance of: scholarly article
title: Visibility of disjoint polygons
zbMATH Open document ID: 0611.68062
DOI: 10.1007/BF01840436
author: T. Asano
author: Tetsuo Asano
author: Hideki Imai
author: Leonidas Guibas
author: John Hershberger
published in: Algorithmica
publication date: 1986-01-01T00:00:00Z
review text: Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in \(O(n^ 2)\) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed in \(O(n^ 2)\) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed in \(O(n^ 2)\) time, improving earlier \(O(n^ 2 \log n)\) results.
Mathematics Subject Classification ID: 68U99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 51M20
zbMATH DE Number: 3988750
zbMATH Keywords: computational geometry
zbMATH Keywords: computer graphics
zbMATH Keywords: robotics
zbMATH Keywords: hidden-line elimination
zbMATH Keywords: data structure
zbMATH Keywords: visibility polygon
zbMATH Keywords: visibility graph
zbMATH Keywords: shortest path
MaRDI profile type: Publication
cites work: The power of geometric duality
cites work: Constructing Arrangements of Lines and Hyperplanes with Applications
cites work: A linear algorithm for computing the visibility polygon from a point
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: Triangulating a simple polygon
cites work: Visibility of a simple polygon
cites work: Euclidean shortest paths in the presence of rectilinear barriers
cites work: Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
Recommended article: Visibility of a simple polygon
Recommended article: Q3808786
Recommended article: Q3139724
Recommended article: Visibility between two edges of a simple polygon
Recommended article: Visibility queries in a polygonal region
Recommended article: Visual distinguishability of polygons
Recommended article: Q3973281
Recommended article: Visibility queries and maintenance in simple polygons
Recommended article: Computing the visibility graph of points within a polygon
description: scientific article; zbMATH DE number 3988750