Fundamenta Informaticae - Volume 22, issue 4

Authors: Edelsbrunner, Herbert | Jaromczyk, Jerzy W.

Article Type: Other

DOI: 10.3233/FI-1995-2246

Citation: Fundamenta Informaticae, vol. 22, no. 4, pp. 307-307, 1995

Authors: Eppstein, David | Miller, Gary L. | Teng, Shang-Hua

Article Type: Research Article

Abstract: We give a deterministic linear time algorithm for finding a “good” sphere separator of a k-ply neighborhood system Φ in any fixed dimension, where a k-ply neighborhood system in $\IR$ d is a collection of n balls such that no points in the space is covered by more than k balls. The separating sphere intersects at most O (k1/d n1−1/d ) balls of Φ and divides the remaining of Φ into two parts: those in the interior and those in the exterior of the sphere, respectively, so that the larger part contains at most δn balls ((d + …1)/(d + 2) < δ < 1). This result improves the O(n2 ) time deterministic algorithm of Miller and Teng [30] and answers a major algorithmic open question posed by Miller, Teng, Thurston, and Vavasis [23, 26]. The deterministic algorithm hinges on the use of a new method for deriving the separator property of neighborhood systems. Using this algorithm, we devise an O(kn+nlogn) time deterministic algorithm for computing the intersection graph of a k-ply neighborhood system. We give an O(nlogn) time algorithm for constructing a linear space, O(logn) query time search structure for a geometric query problem associated with k-ply neighborhood systems, and we use this data structure in an algorithm for approximating the value of k within a constant factor in time O(nlogn). We also develop a deterministic linear time algorithm for finding an O (k1/d n1−1/d )-separator for a k-nearest neighborhood graph in d dimensions. Show more

DOI: 10.3233/FI-1995-2241

Citation: Fundamenta Informaticae, vol. 22, no. 4, pp. 309-329, 1995

Authors: Icking, Christian | Klein, Rolf | Lé, Ngoc-Minh | Ma, Lihong

Article Type: Research Article

Abstract: The bisector systems of convex distance functions in 3-space are investigated and it is shown that there is a substantial difference to the Euclidean metric which cannot be observed in 2-space. This disproves the general belief that Voronoi diagrams in convex distance functions are, in any dimension, analogous to Euclidean Voronoi diagrams. The fact is that more spheres than one can pass through four points in general position. In the L4 -metric, there exist quadrupels of points that lie on the surface of three L4 -spheres. Moreover, for each n ≥ 0 one can construct a smooth and symmetric convex …distance function d and four points that are contained in the surface of exactly 2n+1+ d-spheres, and this number does not decrease if the four points are disturbed independently within 3-dimensional neighborhoods. This result implies that there is no general upper bound to the complexity of the Voronoi diagram of four sites based on a convex distance function in 3-space. Show more

Keywords: Convex distance functions, Voronoi diagrams

DOI: 10.3233/FI-1995-2242

Citation: Fundamenta Informaticae, vol. 22, no. 4, pp. 331-352, 1995

Authors: Kirkpatrick, David | Snoeyink, Jack

Article Type: Research Article

Abstract: Motivated by problems in computational geometry, this paper investigates the complexity of finding a fixed-point of the composition of two or three continuous functions that are defined piecewise. It shows that certain cases require nested binary search taking Θ(log2 n) time. Other cases can be solved in logarithmic time by using a prune-and-search technique that may make tentative discards and later revoke or certify them. This work finds application in optimal subroutines that compute approximations to convex polygons, dense packings, and Voronoi vertices for Euclidean and polygonal distance functions.

DOI: 10.3233/FI-1995-2243

Citation: Fundamenta Informaticae, vol. 22, no. 4, pp. 353-370, 1995

Authors: Bern, Marshall

Article Type: Research Article

Abstract: We give some special-case tetrahedralization algorithms. We first consider the problem of finding a tetrahedralization compatible with, a fixed triangulation of the boundary of a polyhedron. We then adapt our solution to the related problem of compatibly tetrahedralizing the interior and exterior of a polyhedron. We also show how to tetrahedralize the region between nested convex polyhedra with O(nlogn) tetrahedra and no Steiner points.

DOI: 10.3233/FI-1995-2244

Citation: Fundamenta Informaticae, vol. 22, no. 4, pp. 371-384, 1995

Authors: Alon, Noga | Rajagopalan, Sridhar | Suri, Subhash

Article Type: Research Article

Abstract: We study some geometric maximization problems in the Euclidean plane under the non-crossing constraint. Given a set V of 2n points in general position in the plane, we investigate the following geometric configurations using straight-line segments and the Euclidean norm: (i) longest non-crossing matching, (ii) longest non-crossing hamiltonian path, (iii) longest non-crossing spanning tree. We propose simple and efficient algorithms to approximate these structures within a constant factor of optimality. Somewhat surprisingly, we also show that our bounds are within a constant factor of optimality even without the non-crossing constraint, For instance, we give an algorithm to compute a non-crossing …matching whose total length is at least 2/π of the longest (possibly crossing) matching, and show that the ratio 2/π between the non-crossing and crossing matching is the best possible. Perhaps due to their utter simplicity, our methods also seem more general and amenable to applications in other similar contexts. Show more

DOI: 10.3233/FI-1995-2245

Citation: Fundamenta Informaticae, vol. 22, no. 4, pp. 385-394, 1995