International Journal of Computational Geometry & Applications

We study the problem of computing the set of all distant horizons of a terrain, represented as either: (1) the set of all edges that appear on the distant horizon from at least one viewing direction; (2) for every edge e, the set of direction intervals for which e appears on the distant horizon; or (3) a search structure to query for the edges on the distant horizon, or the precise distant horizon, from a fixed viewing direction. We describe an algorithm that solves the first and second forms of the problem in O(n^2+∊) time for any constant ∊ > 0 where n is the number of edges of the terrain. This algorithm can be extended to compute a search structure for (3) in O(n^2+∊) time. The search structure can return the s edges on the distant horizon in O(log n + s) time. We show solving problem (1) is 3SUM hard. Furthermore, we construct a terrain with a single local maximum in which Θ(n) edges each have Θ(n) direction intervals, showing that our solution to (2) cannot be significantly improved, in the worst case, even for such restricted terrains. This takes advantage of a novel construction in which the convex hull of a set of n linearly moving points, whose trajectories do not intersect, changes Ω(n²) times.

We investigate an implementation of the multi-level or ℓ-level k-range data structure. The ℓ-level k-range is compared to naive and R*tree search over N randomly generated k-dimensional points. Results indicate that multi-level k-ranges are not competitive due to their (previously unreported) complexity. We show that storage is S(N,k,ℓ) = O(N^1+2(k-1)/ℓ) and S(N,k) = Θ(N^{1+2(k-1)/log₂N}). Our results also indicate that the ℓ-level k-range requires Q(N,k,ℓ) = O((2ℓ)^k(log N + A)) time for range search, for A = number of points reported in range.

We study the problem of separating n points in the plane, no two of which have the same x- or y-coordinate, using a minimum number of vertical and horizontal lines avoiding the points, so that each cell of the subdivision contains at most one point. Extending previous NP-hardness results due to Freimer et al. we prove that this problem and some variants of it are APX-hard. We give a 2-approximation algorithm for this problem, and a d-approximation algorithm for the d-dimensional variant, in which the points are to be separated using axis-parallel hyperplanes. To this end, we reduce the point separation problem to the rectangle stabbing problem studied by Gaur et al. Their approximation algorithm uses LP-rounding. We present an alternative LP-rounding procedure which also works for the rectangle stabbing problem. We show that the integrality ratio of the LP is exactly 2.

A simple polyhedron is weakly-monotonic in direction provided that the intersection of the polyhedron and any plane with normal is simply-connected (i.e. empty, a point, a line-segment or a simple polygon). Furthermore, if the intersection is a convex set, then the polyhedron is said to be weakly-monotonic in the convex sense. Toussaint¹⁰ introduced these types of polyhedra as generalizations of the 2-dimensional notion of monotonicity. We study the following recognition problems:

Given a simple n-vertex polyhedron in 3-dimensions, we present an O(n log n) time algorithm to determine if there exists a direction such that when sweeping over the polyhedron with a plane in direction , the cross-section (or intersection) is a convex set. If we allow multiple convex polygons in the cross-section as opposed to a single convex polygon, then we provide a linear-time recognition algorithm. For simply-connected cross-sections (i.e. the cross-section is empty, a point, a line-segment or a simple polygon), we derive an O(n²) time recognition algorithm to determine if a direction exists.

We then study variations of monotonicity in 2-dimensions, i.e. for simple polygons. Given a simple n-vertex polygon P, we can determine whether or not a line ℓ can be swept over P in a continuous manner but with varying direction, such that any position of ℓ intersects P in at most two edges. We study two variants of the problem: one where the line is allowed to sweep over a portion of the polygon multiple times and one where it can sweep any portion of the polygon only once. Although the latter problem is slightly more complicated than the former since the line movements are restricted, our solutions to both problems run in O(n²) time.

Given two simple polygons P and Q we define the weight of a bridge (p,q), with p ∈ ρ(P) and q ∈ ρ(Q), where ρ() denotes the compact region enclosed by the boundary of the polygon, between the two polygons as gd(p,P) + d(p,q) + gd(q,Q), where d(p,q) is the Euclidean distance between the points p and q, and gd(x,X) is the geodesic distance between x and its geodesic furthest neighbor on X. Our problem differs from another version of the problem where the additional restriction of requiring the endpoints of the bridge to be mutually visible was imposed. We show that an optimal bridge always exists such that the endpoints of the bridge lie on the boundaries of the two polygons. Using this critical property, we present an algorithm to find an optimal bridge (of minimum weight) in O(n²log n) time. We present a polynomial time approximation scheme that for any ∊ > 0 generates a bridge with objective function within a factor of 1 + ∊ of the optimal value in O(kn log kn) time, where . An improved polynomial time approximation scheme and algorithms for generalized versions of our problems are also discussed.