Parallel computational geometry
From MaRDI portal
Publication:1115600
DOI10.1007/BF01762120zbMath0664.68041MaRDI QIDQ1115600
Bernard Chazelle, Leonidas J. Guibas, Chee-Keng Yap, Alok Aggarwal, Colm P. O'Dunlaing
Publication date: 1988
Published in: Algorithmica (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68U99: Computing methodologies and applications
52A37: Other problems of combinatorial convexity
52A10: Convex sets in (2) dimensions (including convex curves)
52A15: Convex sets in (3) dimensions (including convex surfaces)
Related Items
Finding the Convex Hull of Discs in Parallel, AN IMPROVED HYPERCUBE BOUND FOR MULTISEARCHING AND ITS APPLICATIONS, CONSTRUCTING A STRONGLY CONVEX SUPERHULL OF POINTS, AN OPTIMAL PARALLEL ALGORITHM FOR FINDING THE SMALLEST ENCLOSING TRIANGLE ON A MESH-CONNECTED COMPUTER∗, Parallel Delaunay triangulation for particle finite element methods, GEOMETRIC STREAMING ALGORITHM WITH A SORTING PRIMITIVE, Geometric Streaming Algorithms with a Sorting Primitive, Guarding a terrain by two watchtowers, Fast randomized parallel methods for planar convex hull construction, Optimal parallel quicksort on EREW PRAM, A sublogarithmic convex hull algorithm, An optimal parallel algorithm for linear programming in the plane, Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm, Parallel geometric algorithms for multi-core computers, Sequential and parallel complexity of approximate evaluation of polynomial zeros, 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, Parallel computational geometry, Parallel construction of subdivision hierarchies, 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, 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, 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, Parallel solutions to geometric problems in the scan model of computation, Extremal polygon containment problems, Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems, Constructing arrangements optimally in parallel, Constructing the convex hull of a partially sorted set of points, A nearly optimal deterministic parallel Voronoi diagram algorithm, Parallel geometric algorithms on a mesh-connected computer, Robust algorithms for constructing strongly convex hulls in parallel., \(O(\log \log n)\)-time integer geometry on the CRCW PRAM, A time-optimal parallel algorithm for three-dimensional convex hulls, Finding a closet visible vertex pair between two polygons, Parallel algorithms for arrangements, Sweep methods for parallel computational geometry, Designing checkers for programs that run in parallel, On the multisearching problem for hypercubes, Recursion and parallel algorithms in geometric modeling problems, New sequential and parallel algorithms for computing the \(\beta\)-spectrum, An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram
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
