Computational geometry in a curved world

We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others.     

Approximate Guarding of Monotone and Rectilinear Polygons

We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is OPT for a rectilinear polygon, our algorithm produces a guard set of size O(OPT ²).     

Recognition of largest empty orthoconvex polygon in a point set

An algorithm for computing the maximum area empty isothetic orthoconvex polygon among a set of n points on a 2D rectangular region, is presented. The worst-case time and space complexities of the proposed algorithm are O(n³) and O(n²) respectively.     

Systolic algorithms for computing the visibility polygon and triangulation of a polygonal region

This paper first presents a naive systolic algorithm for finding a closest point for each of n given points in linear time. Then, based on the algorithm, we propose linear-time systolic algorithms for the computation of the visibility polygon and for the trapezoidal partition or triangulation of a polygonal region which may contain holes. The visibility problem among n vertical line segments in the plane is also solved.     

Computational geometry in a curved world

We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others.This research was partially supported by National Science Foundation Grants MCS 83-03926, DCR85-05517, and CCR87-00917.This author's research was also partially supported by an Exxon Foundation Fellowship, by a Henry Rutgers Research Fellowship, and by National Science Foundation Grant CCR88-03549.     

Approximation and inapproximability results for maximum clique of disc graphs in high dimensions

We prove algorithmic and hardness results for the problem of finding the largest set of a fixed diameter in the Euclidean space. In particular, we prove that if A^∗ is the largest subset of diameter r of n points in the Euclidean space, then for every ε>0 there exists a polynomial time algorithm that outputs a set B of size at least |A^∗| and of diameter at most . On the hardness side, roughly speaking, we show that unless P=NP for every ε>0 it is not possible to guarantee the diameter for B even if the algorithm is allowed to output a set of size .     

Fast Range Searching with Delaunay Triangulations

This paper studies the idea of answering range searching queries using simple data structures. The only data structure we need is the Delaunay Triangulation of the input points. The idea is to first locate a vertex of the (arbitrary) query polygon and walk along the boundary of the polygon in the Delaunay Triangulation and report all the points enclosed by the query polygon. For a set of uniformly distributed random points in 2-D and a query polygon the expected query time of this algorithm is O(n ^1/3 + Q + E K + L _r n ^1/2), where Q is the size of the query polygon , {\bf E}K = O(n\bcdot area is the expected number of output points, L _r is a parameter related to the shape of the query polygon and n, and L _r is always bounded by the sum of the edge lengths of . Theoretically, when L _r = O(1/n^1/6) the expected query time is O(n^1/3 + Q + E K), which improves the best known average query time for general range searching. Besides the theoretical meaning, the good property of this algorithm is that once the Delaunay Triangulation is given, no additional preprocessing is needed. In order to obtain empirical results, we design a new algorithm for generating random simple polygons within a given domain. Our empirical results show that the constant coefficient of the algorithm is small, at least for the special (practical) cases when the query polygon is either a triangle (simplex range searching) or an axis-parallel box (orthogonal range searching) and for the general case when the query polygons are generated by our new polygon-generating algorithms and their sizes are relatively small.     

Applications of a two-dimensional hidden-line algorithm to other geometric problems

Recently ElGindy and Avis (EA) presented anO(n) algorithm for solving the two-dimensional hidden-line problem in ann-sided simple polygon. In this paper we show that their algorithm can be used to solve other geometric problems. In particular, triangulating anL-convex polygon and finding the convex hull of a simple polygon can be accomplished inO(n) time, whereas testing a simple polygon forL-convexity can be done inO(n ²) time.     

Finding shortest safari routes in simple polygons

Let P be a simple polygon, and let be a set of disjoint convex polygons inside P, each sharing one edge with P. The safari route problem asks for a shortest route inside P that visits each polygon in . In this paper, we first present a dynamic programming algorithm with running time O(n³) for computing the shortest safari route in the case that a starting point on the route is given, where n is the total number of vertices of P and polygons in . (Ntafos in [Comput. Geom. 1 (1992) 149-170] claimed a more efficient solution, but as shown in Appendix A of this paper, the time analysis of Ntafos' algorithm is erroneous and no time bound is guaranteed for his algorithm.) The restriction of giving a starting point is then removed by a brute-force algorithm, which requires O(n⁴) time. The solution of the safari route problem finds applications in watchman routes under limited visibility.     

A Parallel Algorithm for the Visibility of a Simple Polygon Using Scan Operations

This paper describes a parallel algorithm for computing the visible portion of a simple planar polygon with N vertices from a given point on or inside the polygon. The algorithm accomplishes this in O(k log N) time using O(N/log N) processors, where k is the link-diameter of the polygon in consideration. The link-diameter of a polygon is the maximum number of straight line segments needed to connect any two points within the polygon, where all line segments lie completely within the polygon. The algorithm can also be used to compute the visible portion of the plane given a point outside of the polygon. Except in this case, the parameter k in the asymptotic bounds would be the link diameter of a different polygon. The algorithm is optimal for sets of polygons that have a constant link diameter. It is a rather simple algorithm, and has a very small run time constant, making it fast and practical to implement. The interprocessor communication needed involves only local neighbor communication and scan operations (i.e., parallel prefix operations). Thus the algorithm can be implemented not only on an EREW PRAM, but also on a variety of other more practical machine architectures, such as hypercubes, trees, butterflies, and shuffle exchange networks. The algorithm was implemented on the Connection Machine as well as the MasPar MP- 1, and various performance tests were conducted.     

From the zonotope construction to the Minkowski addition of convex polytopes

A zonotope is the Minkowski addition of line segments in R^d. The zonotope construction problem is to list all extreme points of a zonotope given by its line segments. By duality, it is equivalent to the arrangement construction problem—that is, to generate all regions of an arrangement of hyperplanes.By replacing line segments with convex V-polytopes, we obtain a natural generalization of the zonotope construction problem: the construction of the Minkowski addition of k polytopes. Gritzmann and Sturmfels studied this general problem in various aspects and presented polynomial algorithms for the problem when one of the parameters k or d is fixed. The main objective of the present work is to introduce an efficient algorithm for variable d and k. Here we call an algorithm efficient or polynomial if it runs in time bounded by a polynomial function of both the input size and the output size. The algorithm is a natural extension of a known algorithm for the zonotope construction, based on linear programming and reverse search. It is compact, highly parallelizable and very easy to implement.This work has been motivated by the use of polyhedral computation for optimal tolerance determination in mechanical engineering.     

Dominating set is fixed parameter tractable in claw-free graphs

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K_1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O(k2)n^O(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of K_i,j-free graphs, which exclude, for some fixed i,j∈N, the complete bipartite graph K_i,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of K_i,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K_1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any t∈N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.     

The densest hemisphere problem

Given a set K of n points on the unit sphere S^d in d-dimensional Euclidean space, a hemisphere of S^d is densest if it contains a largest subset of K. In this paper we consider the problem of determining a densest hemisphere and present the following complementary results: (i) a discretized version of the original problem, restated as a feasibility question, is NP-complete when both n and d are arbitrary; (ii) when the number d of dimensions is fixed, there exists a polynomial time algorithm which solves the problem in time O(n_d?1 log n) on a random access machine with unit cost arithmetic operations.     

Approximation algorithms for partitioning a rectangle with interior points

LetR be a rectangle and letP be a set of points located insideR. Our problem consists of introducing a set of line segments of least total length to partition the interior ofR into rectangles. Each rectangle in a valid partition must not contain points fromP as interior points. Since this partitioning problem is computationally intractable (NP-hard), we present efficient approximation algorithms for its solution. The solutions generated by our algorithms are guaranteed to be within three times the optimal solution value. Our algorithm also generates solutions within four times the optimal solution value whenR is a rectilinear polygon. Our algorithm can be generalized to generate good approximation solutions for the case whenR is a rectilinear polygon, there are rectilinear polygonal holes, and the sum of the length of the boundaries is not more than the sum of the length of the edges in an optimal solution.     

Chromatic distribution of k-nearest neighbors of a line segment in a planar colored point set

Let P be a set of n colored points distributed arbitrarily in R². The chromatic distribution of the k-nearest neighbors of a query line segment ? is to report the number of points of each color among the k-nearest points of the query line segment. While solving this problem, we have encountered another interesting problem, namely the semicircular range counting query. Here a set of n points is given. The objective is to report the number of points inside a given semicircular range. We propose a simple algorithm for this problem with preprocessing time and space complexity O(n³), and the query time complexity O(logn). Finally, we propose the algorithm for reporting the chromatic distribution of k nearest neighbors of a query line segment. Using our proposed technique for semicircular range counting query, it runs in O(log²n) time.     

Fast linear expected-time algorithms for computing maxima and convex hulls

This paper examines the expected complexity of boundary problems on a set ofN points inK-space. We assume that the points are chosen from a probability distribution in which each component of a point is chosen independently of all other components. We present an algorithm to find the maximal points usingKN + O (N^1–1/K log^1/K N) expected scalar comparisons, for fixedK 2. A lower bound shows that the algorithm is optimal in the leading term. We describe a simple maxima algorithm that is easy to code, and present experimental evidence that it has similar running time. For fixedK 2, an algorithm computes the convex hull of the set in 2KN + O(N^1–1/K log^1/KN) expected scalar comparisons. The history of the algorithms exhibits interesting interactions among consulting, algorithm design, data analysis, and mathematical analysis of algorithms.This work was performed while this author was visiting AT&T Bell Laboratories.     

On finding a widest empty 1-corner corridor

A 1-corner corridor through a set S of points is an open subset of CH(S) containing no points from S and bounded by a pair of parallel polygonal lines each of which contains two segments. Given a set of n points in the plane, we consider the problem of computing a widest empty 1-corner corridor. We describe an algorithm that solves the problem in O(n⁴logn) time and O(n) space. We also present an approximation algorithm that computes in time a solution with width at least a fraction (1−ε) of the optimal, for any small enough ε>0.     

On exact solutions to the Euclidean bottleneck Steiner tree problem

We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio and there was no known exact algorithm even for k=1 prior to this work. In this paper, we focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an optimal -time exact algorithm for k=1 and an O(n²)-time algorithm for k=2. Also, we present an optimal -time exact algorithm for any constant k for a special case where there is no edge between Steiner points.     

Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives

We consider Markov decision processes (MDPs) with Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes $O(n \cdot\sqrt{m})$ symbolic steps as compared to the previous known algorithm that takes O(n ²) symbolic steps, where n is the number of states and m is the number of edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic algorithm takes $O(n \cdot\sqrt{n})$ symbolic steps, as compared to the previous known O(n ²) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires $O(n \cdot\sqrt{K})$ symbolic steps, where K is the maximal number of edges of strongly connected components (scc’s) of the MDP. The win-lose algorithm requires symbolic computation of scc’s. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5?n symbolic steps, whereas our new algorithm takes 4?n symbolic steps.     

On the geodesic voronoi diagram of point sites in a simple polygon

Given a simple polygon withn sides in the plane and a set ofk point “sites” in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal “geodesic” distance inside the polygon as the metric. We describe anO((n + k) log(n + k) logn)-time algorithm for solving this problem and sketch a fasterO((n + k) log(n + k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.