Parallel computational geometry
From MaRDI portal
Publication:1115600
DOI10.1007/BF01762120zbMath0664.68041OpenAlexW2042607215MaRDI QIDQ1115600
Bernard Chazelle, Leonidas J. Guibas, Colm P. O'Dunlaing, Alok Aggarwal, Chee-Keng Yap
Publication date: 1988
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01762120
Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Other problems of combinatorial convexity (52A37) Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (3) dimensions (including convex surfaces) (52A15)
Related Items
Extremal polygon containment problems, A parallel algorithm for computing Voronoi diagram of a set of circles using touching disc and topology matching, An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram, Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors, \(O(\log \log n)\)-time integer geometry on the CRCW PRAM, Sequential and parallel complexity of approximate evaluation of polynomial zeros, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Parallel Delaunay triangulation for particle finite element methods, A time-optimal parallel algorithm for three-dimensional convex hulls, Finding a closet visible vertex pair between two polygons, GEOMETRIC STREAMING ALGORITHM WITH A SORTING PRIMITIVE, Parallel algorithms for some functions of two convex polygons, An O(log n) time parallel algorithm for triangulating a set of points in the plane, AN OPTIMAL PARALLEL ALGORITHM FOR FINDING THE SMALLEST ENCLOSING TRIANGLE ON A MESH-CONNECTED COMPUTER∗, Parallel algorithms for arrangements, Sweep methods for parallel computational geometry, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Designing checkers for programs that run in parallel, Parallel computational geometry, On the multisearching problem for hypercubes, Parallel construction of subdivision hierarchies, New parallel algorithms for convex hull and triangulation in 3-dimensional space, Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems, The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs, A sublogarithmic convex hull algorithm, An optimal parallel algorithm for linear programming in the plane, Recursion and parallel algorithms in geometric modeling problems, Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm, Geometric Streaming Algorithms with a Sorting Primitive, Parallel computation of distance transforms, Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays, Computational geometry algorithms for the systolic screen, Load-Balancing for Parallel Delaunay Triangulations, Optimal parallel algorithms for point-set and polygon problems, Parallel computational geometry of rectangles, Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers, Fast randomized parallel methods for planar convex hull construction, Line-segment intersection reporting in parallel, Parallel fractional cascading on hypercube multiprocessors, Parallel methods for visibility and shortest-path problems in simple polygons, Constructing the Voronoi diagram of a set of line segments in parallel, CONSTRUCTING A STRONGLY CONVEX SUPERHULL OF POINTS, Parallel geometric algorithms for multi-core computers, Guarding a terrain by two watchtowers, Constructing arrangements optimally in parallel, Constructing the convex hull of a partially sorted set of points, Optimal parallel quicksort on EREW PRAM, A nearly optimal deterministic parallel Voronoi diagram algorithm, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Parallel geometric algorithms on a mesh-connected computer, Robust algorithms for constructing strongly convex hulls in parallel., New sequential and parallel algorithms for computing the \(\beta\)-spectrum, Parallel solutions to geometric problems in the scan model of computation, Finding the Convex Hull of Discs in Parallel, AN IMPROVED HYPERCUBE BOUND FOR MULTISEARCHING AND ITS APPLICATIONS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast detection of polyhedral intersection
- Sorting in \(c \log n\) parallel steps
- The complexity of elementary algebra and geometry
- Geometric applications of a matrix-searching algorithm
- Parallel computational geometry
- Voronoi diagrams from convex hulls
- Maintenance of configurations in the plane
- A combinatorial theorem in plane geometry
- Reporting and counting segment intersections
- Minimum area circumscribing polygons
- Finding Extremal Polygons
- An Efficient Parallel Biconnectivity Algorithm
- Finding the smallest triangles containing a given convex polygon
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Triangulation and shape-complexity
- An optimal algorithm for finding minimal enclosing triangles
- Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
- Segments, rectangles, contours
- An O(logn) parallel connectivity algorithm
- Determining the minimum-area encasing rectangle for an arbitrary closed curve
- Parallelism in Comparison Problems
- Convex hulls of finite sets of points in two and three dimensions
- The Parallel Evaluation of General Arithmetic Expressions
