This paper studies the problem of enumerating all maximal collinear subsets of size at least three in a given set of @math points. An algorithm for this problem, besides solving degeneracy testing and the exact fitting problem, can also help with other problems, such as point line cover and general position subset selection. The classic algorithm of Edelsbrunner and Guibas can find these subsets in @math time in the dual plane. We present an alternative algorithm that, although asymptotically slower than their algorithm in the worst case, is simpler to implement and more amenable to parallelization. If the input points are decomposed into @math convex polygons, our algorithm has time complexity @math and space complexity @math . Our algorithm can be parallelized on the CREW PRAM with time complexity @math using @math processors.
Other methods have been presented to partition the arrangement into smaller regions with fewer points and use the sequential algorithm for sweeping these regions in parallel (e.g. @cite_1 and @cite_14 ). They are usually based on the assumption that the points are in general position. Such partitions yield poor performance, when this assumption is violated as it is the case in the problem of finding collinear points. Similar parallel sweeping methods have been presented for specific applications (e.g., rectangle intersection @cite_9 and hidden surface elimination @cite_20 ), in which there are fewer events than the number of intersections in the worst case (for finding collinear subsets @math ). More recently, presented a plane sweep algorithm that divides the plane into vertical slabs perpendicular to the sweep line, which has time complexity @math with @math processors for @math intersections @cite_0 , whose cost is more than our algorithm.
@cite_14 @cite_9 @cite_1 @cite_0 @cite_20
2121315472 1997248273 2038730428 2000697206
In this paper we give efficient parallel algorithms for a number of problems from computational geometry by using versions of parallel plane sweeping. We illustrate our approach with a number of applications, which include:General hidden-surface elimination (even if the overlap relation contains cycles).CSG boundary evaluation.Computing the contour of a collection of rectangles.Hidden-surface elimination for rectangles. There are interesting subproblems that we solve as a part of each parallelization. For example, we give an optimal parallel method for building a data structure for line-stabbing queries (which, incidentally, improves the sequential complexity of this problem). Our algorithms are for the CREW PRAM, unless otherwise noted. Parallel algorithms used in Very Large Scale Integration physical design bring significant challenges for their efficient and effective design and implementation. The rectangle intersection problem is a subset of the plane sweep problem, a topic of computational geometry and a component in design rule checking, parasitic resistance-capacitance extraction, and mask processing flows. A variant of a plane sweep algorithm that is embarrassingly parallel and therefore easily scalable on multicore machines and clusters, while exceeding the best-known parallel plane sweep algorithms on real-world tests, is presented in this letter. Abstract Sweeping a collection of figures in the Euclidean plane with a straight line is one of the novel algorithmic paradigms that have emerged in the field of computational geometry. In this paper we demonstrate the advantages of sweeping with a topological line that is not necessarily straight. We show how an arrangement of n lines in the plane can be swept over in O ( n 2 ) time and O(n) space by a such a line. In the process each element, i.e., vertex, edge, or region, is visited once in a consistent ordering. Our technique makes use of novel data structures which exhibit interesting amortized complexity behavior; the result is an algorithm that improves upon all its predecessors either in the space or the time bounds, as well as being eminently practical. Numerous applications of the technique to problems in computational geometry are given—many through the use of duality transforms. Examples include solving visibility problems, detecting degeneracies in configurations, computing the extremal shadows of convex polytopes, and others. Even though our basic technique solves a planar problem, its applications include several problems in higher dimensions. Ray tracing requires testing of many rays to determine intersections with objects. A way of reducing the computation is to organize objects into hierarchical data structures. We examine two heuristics for space subdivisions using bintrees, one based on the intuition that surface area is a good estimate of intersection probability, one based on the fact that the optimal splitting plane lies between the spatial median and the object median planes of a volume. Traversal algorithms using cross links between nodes are presented as generalizations of ropes in octrees. Simulations of the surface area heuristic and the cross link scheme are presented. These results generalize to other hierarchical data structures.