Search

We study the problem of guarding an orthogonal art gallery with security cameras sliding back and forth along straight tracks. We show that if only vertical (alternatively, horizontal) tracks are allowed, then a solution minimizing the number of tracks can be found in polynomial time, and if both orientations are allowed, then a 2-approximation can be found in polynomial time for x-monotone galleries. [ABSTRACT FROM AUTHOR]

A decomposition of a polygon P is a set of polygons whose geometric union is exactly P. We study a polygon decomposition problem that is equivalent to the Orthogonal Art Gallery problem. Two points are r-visible if the orthogonal bounding rectangle for p and q lies within P. A polygon P is an r-star if there exists a point k ∈ P such that for each point q ∈ P, q is r-visible from k. In this problem we seek a minimum cardinality decomposition of a polygon into r-stars. We show how to compute the minimum r-star cover of an orthogonal polygon in polynomial time. [ABSTRACT FROM AUTHOR]

We address the problem of continuously transforming or morphing one simple polyline into another so that every point p of the initial polyline moves to a point q of the final polyline using the geodesic shortest path from p to q. We optimize the width of the morphing, that is, the longest path made by a point on the polyline. We present an algorithm for finding the minimum width morphing in O(n²) time using O(n) space, where n is the total number of vertices of polylines. This improves the previous algorithm[sup 7] by a factor of log² n. [ABSTRACT FROM AUTHOR]

In this paper, we study several geometric path query problems. Given a scene of disjoint polygonal obstacles with totally n vertices in the plane, we construct efficient data structures that enable fast reporting of an "optimal" obstacle-avoiding path (or its length, cost, directions, etc) between two arbitrary query points s and t that are given in an online fashion. We consider geometric paths under several optimality criteria: L[sub m] length, number of edges (called links), monotonicity with respect to a certain direction, and some combinations of length and links. Our methods are centered around the notion of gateways, a small number of easily identified points in the plane that control the paths we seek. We give efficient solutions for several special cases based upon new geometric observations. We also present solutions for the general cases based upon the computation of the minimum size visibility polygon for query points. [ABSTRACT FROM AUTHOR]

A strategy is presented to find a set of points that yields a Conforming Delaunay tetrahedralization of a three-dimensional Piecewise-Linear complex (PLC). This algorithm is novel because it imposes no angle restrictions on the input PLC. In the process, an algorithm is described that computes a planar conforming Delaunay triangulation of a Planar Straight-Line Graph (PSLG) such that each triangle has a bounded circumradius, which may be of independent interest. [ABSTRACT FROM AUTHOR]

We present a new algorithm for labeling points with circles of equal size. Our algorithm tries to maximize the label size. It improves the approximation factor of the only known algorithm for this problem by more than 50% to about 1/20. At the same time, our algorithm keeps the O(n log n) time bound of its predecessor. In addition, we show that the decision problem is NP-hard and that it is NP-hard to approximate the maximum label size beyond a certain constant factor. [ABSTRACT FROM AUTHOR]

Separating an object in an image from its background is a central problem (called segmentation) in pattern recognition and computer vision. In this paper, we study the computational complexity of the segmentation problem, assuming that the sought object forms a connected region in an intensity image. We show that the optimization problem of separating a connected region in a grid of N x N pixels is NP-hard under the interclass variance, a criterion that is often used in discriminant analysis. More importantly, we consider the basic case in which the object is bounded by two x-monotone curves (i.e., the object itself is x-monotone), and present polynomial-time algorithms for computing the optimal segmentation. Our main algorithm for exact optimal segmentation by two x-monotone curves runs in O(N[sup 4]) time; this algorithm is based on several techniques such as a parametric optimization formulation, a hand-probing algorithm for the convex hull of an unknown planar point set, and dynamic programming using fast matrix searching. Our efficient approximation scheme obtains an ∈-approximate solution in O(∈[sup -1]N² log L) time, where ∈ is any fixed constant with 1 > ∈ > 0, and L is the total sum of the absolute values of the brightness levels of the image. [ABSTRACT FROM AUTHOR]

We present efficient algorithms for several instances of the following facility location problem. Place k obnoxious facilities, with respect to n given demand sites and m given regions, where the goal is to maximize the minimal distance between a demand site and a facility, under the constraint that each of the regions must contain at least one facility. We also present an efficient solution to the following planar problem that arises as a subproblem. Given n transmitters, each of range r, construct a compact data structure that supports coverage queries, i.e., determine whether a query polygonal/rectangular region is fully covered by the transmitters. [ABSTRACT FROM AUTHOR]

We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in \R d , is Θ (n d-1 ) . This improves substantially the upper bound of O(n 2d-2 ) known for general convex sets [9]. We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit disks in the plane is two, improving the previous upper bound of three given in [5]. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

An n-vertex simple polygon P is said to have a Hamiltonian Triangulation if it has a triangulation whose dual graph contains a hamiltonian path. Such triangulations are useful in fast rendering engines in Computer Graphics. We give a new characterization of polygons with hamiltonian triangulations and use it to devise O(n log n)-time algorithms to recognize such polygons. We also give efficient algorithms for several related problems. [ABSTRACT FROM AUTHOR]

In the p-piercing problem, a set S of nd-dimensional objects is given, and one has to compute a piercing set for S of size p, if such a set exists. We consider several instances of the 3-piercing problem that admit linear or almost linear solutions: (i) If S consists of axis-parallel boxes in R[sup d], then a piercing triplet for S can be found (if such a triplet exists) in O(n log n) time, for 3 ≤ d ≤ 5, and in [formula] time, for d ≥ 6. Based on the solutions for 3 ≤ d ≤ 5, efficient solutions are obtained to the corresponding 3-center problem — Given a set P of n points of R[sup d], compute the smallest edge length λ such that P can be covered by the union of three axis-parallel cubes of edge length λ. (ii) If S consists of homothetic triangles in the plane, or of 4-oriented trapezoids in the plane, then a piercing triplet can be found in O(n log n) time. [formula available in full text]. [ABSTRACT FROM AUTHOR]

A double-ray configuration is a configuration in the plane consisting of two rays emanating from one point. Given a set S of n points in the plane, we want to find a double-ray configuration that minimizes the Hausdorff distance from S to this configuaration. We call this problem the double-ray center problem. We present an efficient algorithm for computing the double-ray center for set S of n points in the plane which runs in time O(n[sup 3]α(n)log[sup 2]n). [ABSTRACT FROM AUTHOR]

We discuss rectangle and box visibility representations of graphs in 3-dimensional space. In these representations, vertices are represented by axis-aligned disjoint rectangles or boxes. Two vertices are adjacent if and only if their corresponding boxes see each other along a small axis-parallel cylinder. We concentrate on lower and upper bounds for the size of the largest complete graph that can be represented. In particular, we examine these bounds under certain restrictions: What can be said if we may only use boxes of a limited number of shapes? Some of the results presented are as follows: • There is a representation of K[sub 8] by unit boxes. A special case arises for rectangle visibility graphs, where no two boxes can see each other in the x- or y-directions, which means that the boxes have to see each other in z-parallel direction. This special case has been considered before; we give further results, dealing with the aspects arising from limits on the number of shapes. [ABSTRACT FROM AUTHOR]

Let S be a set of n points in the plane. We study the following problem: Partition S by a line into two subsets S[sub a] and S[sub b] such that max{f(S[sub a]), f(S[sub b])} is minimal, where f is any monotone function defined over 2[sup S]. We first present a solution to the case where the points in S are the vertices of a convex polygon and apply it to some common cases — f(S′) is the perimeter, area, or width of the convex hull of S′⊆S — to obtain linear solutions (or O(n log n) solutions if the convex hull of S is not given) to the corresponding problems. This solution is based on an efficient procedure for finding a minimal entry in matrices of some special type, which we believe is of independent interest. For the general case we present a linear space solution which is in some sense output sensitive. It yields solutions to the perimeter and area cases that are never slower and often faster than the best previous solutions. [ABSTRACT FROM AUTHOR]