Search

We present a new approach, called topological peeling, for traversing a portion AR of the arrangement formed by n lines within a convex region R on the plane. Topological peeling visits the cells of A[SUBR] in a fashion of propagating a "wave" of a special shape (called a double-wriggle curve) starting at a single source point. This special traversal fashion enables us to solve several problems (e.g., computing shortest paths) on planar arrangements to which previously best known arrangement traversal techniques such as topological sweep and topological walk may not be directly applicable. Our topological peeling algorithm takes O(K + nlog(n + r)) time and O(n + r) space, where K is the number of cells in A[SUBR] and r is the number of boundary vertices of R. Comparing with topological walk, topological peeling uses a simpler and more efficient way to sweep different types of lines, and relies heavily on exploring small local structures, rather than a much larger global structure. Experiments show that, on average, topological peeling outperforms topological walk by 10-25 1241328n execution time. [ABSTRACT FROM AUTHOR]

Image segmentation with specific constraints has found applications in several areas such as biomedical image analysis and data mining. In this paper, we study the problem of segmenting star-shaped and smooth objects in 2-D and tubular objects in 3-D images. Image objects of these shapes are often studied in medical applications. For the 2-D case of the problem, we present an O(IJ log J) time algorithm, improving the previously best known O(IJ[sup 2]M) time algorithm by a factor of [formula] time, where the size of the input 2-D image is I × J and M is the smoothness parameter with 1 ≤ M ≤ J. Our 2-D algorithm is based on a combination of dynamic programming and divide-and-conquer strategy, and on computing an optimal path in an implicitly represented graph. We also prove that a generalized version of the 3-D case of the problem is NP-hard. [formula available in full text]. [ABSTRACT FROM AUTHOR]

This paper presents how the space of spheres and shelling may be used to delete a point from a d-dimensional triangulation efficiently. In dimension two, if k is the degree of the deleted vertex, the complexity is O(k log k), but we notice that this number only applies to low cost operations, while time consuming computations are only done a linear number of times. This algorithm may be viewed as a variation of Heller's algorithm,[sup 1,2] which is popular in the geographic information system community. Unfortunately, Heller algorithm is false, as explained in this paper. [ABSTRACT FROM AUTHOR]

Let π(a, b) denote the shortest path between two points a, b inside a simple polygon P, which totally lies in P. The geodesic distance between a and b in P is defined as the length of π(a, b), denoted by gd(a, b), in contrast with the Euclidean distance between a and b in the plane, denoted by d(a, b). Given two disjoint polygons P and Q in the plane, the bridge problem asks for a line segment (optimal bridge) that connects a point p on the boundary of P and a point q on the boundary of Q such that the sum of three distances gd(p', p), d(p, q) and gd(q, q'), with any p' ∈ P and any q' ∈ Q, is minimized. We present an O(n log³ n) time algorithm for finding an optimal bridge between two simple polygons. This significantly improves upon the previous O(n²) time bound. Our result is obtained by making substantial use of a hierarchical structure that consists of segment trees, range trees and persistent search trees, and a structure that supports dynamic ray shooting and shortest path queries as well. [ABSTRACT FROM AUTHOR]

In this paper, we propose new rules of advancing edges for computing the intersection of a pair of convex polygons in the plane. These rules have no ambiguities when extended into the spherical surface, differently from those of O'Rourke et al..[sup 4] Finally, we design a linear-time algorithm for computing the intersection of a pair of spherical convex polygons, and prove its correctness. [ABSTRACT FROM AUTHOR]

Assume a robot that, when directed to move in a particular direction, is guaranteed to move inside a cone of angle α centered at the specified direction. The robot has to reach a convex polygonal goal G, while avoiding polygonal obstacles of complexity n. We show that the complexity of the safe region, from where the robot can reach the goal with a single motion with uncertainty α, is O(m + n), and can be computed in time O((m + n) log(m + n)), if α is assumed constant. [ABSTRACT FROM AUTHOR]

A rectilinear map consists of a set of mutually non-intersecting rectilinear (i.e., horizontal or vertical) line segments, and each segment is allowed to use a rectangular label of height B and length the same as the segment. Sliding labels are not restricted to any finite number of predefined positions but can slide and be placed at any position as long as it intersects the segment. This paper considers three versions of the problem of labeling a rectilinear map with sliding labels and presents efficient exact and approximation algorithms for them. [ABSTRACT FROM AUTHOR]

The 1-searcher is a mobile guard whose visibility is limited to a ray emanating from his position, where the direction of the ray can be changed continuously with bounded angular rotation speed. Given a polygonal region P with a specified boundary point d, is it possible for a I-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within P, before the intruder reaches d? We decide this question in O(n log n)-time for an n-sided polygon. Our main result is a simple characterization of the class of polygons (with a boundary point d) that admits such a search strategy. We also present a simple O(n²)-time algorithm for constructing a search schedule, if one exists. Finally, we compare the search capability of a 1-searcher with that of two guards. [ABSTRACT FROM AUTHOR]

Let X and Y be two disjoint sets of points in the plane such that X = Y and no three points of X ∪ Y are on the same line. Then we can draw an alternating Hamilton cycle on X U Y in the plane which passes through alternately points of X and those of Y, whose edges are straight-line segments, and which contains at most X - 1 crossings. Our proof gives an O(n² logn) time algorithm for finding such an alternating Hamilton cycle, where n = X. Moreover we show that the above upper bound X - 1 on crossing number is best possible for some configurations. [ABSTRACT FROM AUTHOR]

We study the art gallery problem restricted to edge guards and straight walkable polygons. An edge guard is the guard that patrols individual edges of the polygon. A simple polygon P is called straight walkable if there are two vertices s and t in P and we can move two points montonically on two polygonal chains of P from s to t, one clockwise and the other counterclockwise, such that two points are always mutually visible. For instance, monotone polygons and spiral polygons are straight walkable. We show that └(n+2)/5┘ edge guards are always sufficient to watch and n-vertex gallery of this type. Furthermore, we also show that if the given polygon is straight walkable and rectilinear, then └(n+3)/6┘ edge guards are sufficient. Both of our upper bounds match the known lower bounds. [ABSTRACT FROM AUTHOR]

We consider some intersection problems on segments of R[sup 2] in the partially dynamic setting called boundary update, where updates occur at the boundary of a given region. In particular, we maintain a set S of line segments under (boundary) insertions and deletions, such that, given a line segment ℓ either of fixed slope or originating from a fixed point and given a point p∈S∩ℓ, we can efficiently and orderly report all segments intersecting ℓ; insertions/deletions of segments occur at the boundaries of a vertical infinite slab. We provide practical algorithms requiring O(|S|) space, O(log |S|) time per update and O(||) time per query, where k is the number of reported segments. Our results allow both modeling a moving window over a larger data set and answering segment intersection queries at an extra query cost of O(log |S|); also, they provide a methodology for designing access methods to temporal databases as well as a new kind of partially persistent lists. [ABSTRACT FROM AUTHOR]