A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

On the minimum size of visibility graphs

In this paper we give tight lower bounds on the size of the visibility graph, the contracted visibility graph, and the bar-visibility graph of n disjoint line segments in the plane, according to their vertex-connectivity.     

An optimal visibility graph algorithm for triangulated simple polygons

LetP be a triangulated simple polygon withn sides. The visibility graph ofP has an edge between every pair of polygon vertices that can be connected by an open segment in the interior ofP. We describe an algorithm that finds the visibility graph ofP inO(m) time, wherem is the number of edges in the visibility graph. Becausem can be as small asO(n), the algorithm improves on the more general visibility algorithms of Asanoet al. [AAGHI] and Welzl [W], which take (n ²) time, and on Suri'sO(m logn) visibility graph algorithm for simple polygons [S].This work was supported in part by a U.S. Army Research Office fellowship under agreement DAAG29-83-G-0020.     

Visibility of disjoint polygons

Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n ²) time and space, a data structure from which inO(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 inO(n ²) 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 inO(n ²) time, improving earlierO(n ² logn) results.     

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

Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems.Work on this paper by this author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, the IBM Corporation, and from the U.S.-Israel Binational Science Foundation.Work on this paper by this author has been supported by National Science Foundation Grant DCR-86-05962.     

VC-dimension of perimeter visibility domains

We obtain an upper bound of 7 for the VC-dimension of Perimeter Visibility Domains in simple polygons.     

Constructing the visibility graph for n-line segments in O(n2) time

Given a set S of line segments in the plane, its visibility graph G_S is the undirected graph which has the endpoints of the line segments in S as nodes and in which two nodes (points) are adjacent whenever they ‘see’ each other (the line segments in S are regarded as nontransparent obstacles). It is shown that G_S can be constructed in O(n²) time and space for a set S of n nonintersecting line segments. As an immediate implication, the shortest path between two points in the plane avoiding a set of n nonintersecting line segments can be computed in O(n²) time and space     

An algorithm for recognizing palm polygons

A polygonP is said to be apalm polygon if there exists a pointxP such that the Euclidean shortest path fromx to any pointyP makes only left turns or only right turns. The set of all such pointsx is called thepalm kernel. In this paper we propose an O(E) time algorithm for recognizing a palm polygonP, whereE is the size of the visibility graph ofP. The algorithm recognizes the given polygonP as a palm polygon by computing the palm kernel ofP. If the palm kernel is not empty,P is a palm polygon.The extended abstract of this paper was reported at the Second Canadian Conference in Computational Geometry, pp. 246–251, 1990     

Characterizing and recognizing the visibility graph of a funnel-shaped polygon

A funnel, which is notable for its fundamental role in visibility algorithms, is defined as a polygon that has exactly three convex vertices, two of which are connected by a boundary edge. In this paper we investigate the visibility graph of a funnel which we call an F-graph.We first present two characterizations of an F-graph, one of whose sufficiency proof itself is a linear time Real RAM algorithm for drawing a funnel on the plane that corresponds to an F-graph. We next give a linear-time algorithm for recognizing an F-graph. When the algorithm recognizes an F-graph, it also reports one of the Hamiltonian cycles defining the boundary of its corresponding funnel. This recognition algorithm takes linear time even on a RAM.We finally show that an F-graph is weakly triangulated and therefore perfect, which agrees with the fact that perfect graphs are related to geometric structures.This work was supported in part by the Korea Science and Engineering Foundation under Grant 91-01-01.     

Shortest paths in simple polygons with polygon-meet constraints

We study a constrained version of the shortest path problem in simple polygons, in which the path must visit a given target polygon. We provide a worst-case optimal algorithm for this problem and also present a method to construct a subdivision of the simple polygon to efficiently answer queries to retrieve the shortest polygon-meeting paths from a single-source to the query point. The algorithms are linear, both in time and space, in terms of the complexity of the two polygons.     

Some chain visibility problems in a simple polygon

In this paper, the notions of convex chain visibility and reflex chain visibility of a simple polygonP are introduced, and some optimal algorithms concerned with convex- and reflex-chain visibility problems are described. For a convex-chain visibility problem, two linear-time algorithms are exhibited for determining whether or notP is visible from a given convex chain; one is the turn-checking approach and the other is the decomposition approach based on checking edge visibilities. We also present a linear-time algorithm for finding, if any, all maximal convex chains of a given polygonP from whichP is visible, where a maximal convex chain is a convex chain which does not properly include any other convex chains. It can be made by showing that there can be at most four visible maximal convex chains inP with an empty kernel. By similar arguments, we show that the same problems for reflex chain visibility can be easily solved in linear time.     

A provably fast linear-expected-time maxima-finding algorithm

In a recent paper Bentleyet al. [1] presented some fast (low-multiplicative constants) linear-expected-time algorithms for finding the maxima ofN points chosen independently identically distributed (i.i.d.) from a Component Independent (CI) distribution. They also presented another algorithm, the Move-To-Front (MTF) algorithm, which empirical evidence suggests runs faster than the other algorithms. They conjectured that the MTF algorithm runs inN+o(N) expected time. In this paper we prove their conjecture forN points chosen i.i.d. from any two-dimensional distribution. The proof mixes probabilistic and amortized techniques.This work was supported in part by NSF Grant DCR-8605962 and ONR Research Grant N00014-87-K0460. The later part of it was supported by a Chateaubriand Fellowship from the French Ministere des Affaires Etrangeres and by the European Community, Esprit II Basic Research Action Program Number 3075 (ALCOM).     

An approximative solution to the Zookeeper's Problem

Consider a simple polygon P containing disjoint convex polygons each of which shares an edge with P. The Zookeeper's Problem then asks for the shortest route in P that visits all convex polygons without entering their interiors. Existing algorithms that solve this problem run in time super-linear in the size of P and the convex polygons. They also suffer from numerical problems.In this paper, we shed more light on the problem and present a simple linear time algorithm for computing an approximate solution. The algorithm mainly computes shortest paths and intersections between lines using basic data structures. It does not suffer from numerical problems. We prove that the computed approximation route is at most 6 times longer than the shortest route in the exact solution.     

Parallel methods for visibility and shortest-path problems in simple polygons

In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.This research was announced in preliminary form in theProceedings of the 6th ACM Symposium on Computational Geometry, 1990, pp. 73–82. The research of Michael T. Goodrich was supported by the National Science Foundation under Grants CCR-8810568 and CCR-9003299, and by the NSF and DARPA under Grant CCR-8908092.     

A fast algorithm for computing a longest common increasing subsequence

Let A=〈a₁,a₂,…,am〉 and B=〈b₁,b₂,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai₁=bj₁,ai₂=bj₂,…,ail=bjl〉, where i₁<i₂<?<il and j₁<j₂<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space.     

A linear-time algorithm for constructing a circular visibility diagram

To computer circular visibility inside a simple polygon, circular arcs that emanate from a given interior point are classified with respect to the edges of the polygon they first intersect. Representing these sets of circular arcs by their centers results in a planar partition called the circular visibility diagram. AnO(n) algorithm is given for constructing the circular visibility diagram for a simple polygon withn vertices.     

Epileptic seizure detection in EEGs signals using a fast weighted horizontal visibility algorithm

This paper proposes a fast weighted horizontal visibility graph constructing algorithm (FWHVA) to identify seizure from EEG signals. The performance of the FWHVA is evaluated by comparing with Fast Fourier Transform (FFT) and sample entropy (SampEn) method. Two noise-robustness graph features based on the FWHVA, mean degree and mean strength, are investigated using two chaos signals and five groups of EEG signals. Experimental results show that feature extraction using the FWHVA is faster than that of SampEn and FFT. And mean strength feature associated with ictal EEG is significant higher than that of healthy and inter-ictal EEGs. In addition, an 100% classification accuracy for identifying seizure from healthy shows that the features based on the FWHVA are more promising than the frequency features based on FFT and entropy indices based on SampEn for time series classification.     

A fast deterministic smallest enclosing disk approximation algorithm

We describe a simple and fast -time algorithm for finding a (1+?)-approximation of the smallest enclosing disk of a planar set of n points or disks. Experimental results of a readily available implementation are presented.