International Journal of Computational Geometry & Applications

A set of n distinct points in the plane defines lines by joining each pair of distinct points. The median slope of these O(n²) lines was proposed by Theil as a robust estimator for the slope of the line of best fit for the points. We present a randomized algorithm for selecting the k-th smallest slope of such a set of lines which runs in expected O(n log n) time. An efficient implementation of the algorithm and practical experience with the algorithm are discussed.

A new generalized Voronoi diagram is defined on the surface of a river with uniform flow; a point belongs to the territory of a site if and only if a boat starting from the site can reach the point faster than a boat starting from any other site. If the river runs slower than the boat, the Voronoi diagram has the same topological structure as the ordinary Voronoi diagram, and hence can be constructed from the ordinary Voronoi diagram by a certain transformation. If the river runs faster than the boat, on the other hand, the topological structure of the diagram becomes different from the ordinary one, but it can be constructed by the plane sweep technique. Moreover, Fortune’s plane sweep algorithm for constructing the ordinary Voronoi diagram can be interpreted as the algorithm for constructing the Voronoi diagram in a river in which the water flows at the same speed as the boat.

In this paper, we study the enumerative versions of the interdistance in terdis stance ranking and selection problems in space, namely, the fixed-radius near neighbors and interdistance enumeration problems, respectively. The input to the fixed-radius near neighbors problem is a set of n points S⊆ℜ^d and a nonnegative real number δ, and the output consists of all pairs of points within interdistance δ. We give an algorithm which, after an O(n log n) time preprocessing step, answers a fixed-radius near neighbors query with respect to an L_p metric in O(n+ρ(δ)) time, where ρ(δ) is the rank of δ. The space needed is O(n). The input to the interdistance enumeration problem is a set of n points S⃄ℜ^d and an integer k, , and the output is a set of point pairs, each corresponding to an interdistance having length less than or equal to the interdistance with rank k. We offer an O(n log n+k) time, O(n+k) space algorithm for this problem. This algorithm also works for any L_p metric.

We consider the problem of finding a rectilinear path between two designated points in the presence of rectilinear obstacles subject to various optimization functions in terms of the number of bends and the total length of the path. Specifically we are interested in finding a minimum bend shortest path, a shortest minimum bend path or a least-cost path where the cost is defined as a function of both the length and the number of bends of the path. We provide a unified approach by constructing a path-preserving graph. guaranteed to preserve all these three kinds of paths and give an O(K+e log e) algorithm to find them, where e is the total number of obstacle edges, and K is the number of intersections between tracks from extreme point and other tracks (defined in the text). K is bounded by O(et), where t is the number of extreme edges. In particular, if the obstacles are rectilinearly convex, then K is O(ne), where n is the number of obstacles. Extensions are made to find a shortest path with a bounded number of bends and a minimum-bend path with a bounded length. When a source point and obstacles are pre-given, queries for the assorted paths from the source to given points can be handled in O(log e+k) time after O(K+e log e) preprocessing, where k is the size of the goal path. The trans-dichotomous algorithm of Fredman and Willard⁸ and the running time for these problems are also discussed.

In this paper, we give an algorithm that triangulates the convex hull of a three dimensional point set with guaranteed quality tetrahedra. Good triangulations of convex polyhedra are a special case of this problem. We also give a bound on the number of additional points used to achieve these guarantees and report on the techniques we use to produce a robust implementation of this algorithm under finite precision arithmetic.

We use here the results on the influence graph¹ to adapt them for particular cases where additional information is available. In some cases, it is possible to improve the expected randomized complexity of algorithms from O(n log n) to O(n log^⋆ n). This technique applies in the following applications: triangulation of a simple polygon, skeleton of a simple polygon, Delaunay triangulation of points knowing the EMST (euclidean minimum spanning tree).