Narrow Results

In this paper we propose a parallel algorithm to construct a one-sided monotone polygon from a Hamiltonian 2-separator chordal graph. The algorithm requires O(log n) time and O(n) processors on the CREW PRAM model, where n is the number of vertices and m is the number of edges in the graph. We also propose parallel algorithms to recognize Hamiltonian 2-separator chordal graphs and to construct a Hamiltonian cycle in such a graph. They run in O(log² n) time using O(mn) processors on the CRCW PRAM model and O(log² n) time using O(m) processors on the CREW PRAM model, respectively.

In this paper we report on a set of six necessary conditions that must be satisfied by the edge visibility graph of an orthogonal polygon with holes. We have also proved the following significant result: If G is a connected, bipartite, planar, and irreducible (in a sense defined in the paper) graph then it can be realized (that is, there is a corresponding orthogonal polygon with holes) up to leaf addition.

Given a set S of n non-intersecting line segments in the plane, we vpresent a new technique for efficiently traversing the endpoint visibility graph of S to solve a variety of visibility problems in output sensitive time. In particular, we develop two techniques to compute the 2n visibility polygons of the endpoints of S, in output sensitive time.

Depth-first spiralling is a technique that relies on the ordered endpoint visibility graph information to traverse the endpoints of S in a spiral-like manner using a combination of Jarvis' March and depth-first search. It is a practical method and has been implemented in C++ using LEDA.

In this paper, we consider two distinct problems related to complexity aspects of the visibility graphs of simple polygons. Recognizing visibility graphs is a long-standing open problem. It is not even known whether visibility graph recognition is in NP. That visibility graph recognition is in NP would be established if we could demonstrate that any n vertex visibility graph is realized by a polygon which can be drawn on an exponentially-sized grid. This motivates a study of the area requirements for realizing visibility graphs. In this paper, we prove:

• Θ(n³) area is necessary and sufficient to realize the complete visibility graph K_n.

• There exist visibility graphs which require exponential area to realize.

• Any maximal outerplanar graph of diameter d can be realized in O(d² · 2^d) area, which can be as small as O(n log² n) for a balanced mop. Linear maximal outer-planar graphs can be realized in O(n⁸) area.

The second part of this paper considers the complexity of specific optimization problems on visibility graphs. Given a polygon P, we show that finding a maximum independent set, minimum vertex cover, or maximum dominating set in the visibility graph of P are all NP-complete. Further we show that for polygons P₁ and P₂, the problem of testing if they have isomorphic visibility graphs is isomorphism-complete. These problems remain hard when given the visibility graphs as input.

Recognizing 3D objects from their 2D silhouettes is a popular topic in computer vision. Object reconstruction can be performed using the volume intersection approach. The visual hull of an object is the best approximation of an object that can be obtained by volume intersection. From the point of view of recognition from silhouettes, the visual hull can not be distinguished from the original object. In this paper, we present efficient algorithms for computing visual hulls. We start with the case of planar figures (polygons and curved objects) and base our approach on an efficient algorithm for computing the visibility graph of planar figures. We present and tackle many topics related to the query of visual hulls and to the recognition of objects equal to their visual hulls. We then move on to the 3-dimensional case and give a flavor of how it may be approached.

We consider the visibility graphs for superpositions of fractional Brownian motions with different Hurst exponents. It is found that the degree distributions obey power-law. The components with lower Hurst exponents dominate the heterogeneity behaviors of the visibility graphs. These findings are helpful for us to understand the characteristics of visibility graphs for real-world time series.