Parallel construction of subdivision hierarchies

DOI10.1016/0022-0000(89)90042-1MaRDI QIDQ1124347zbMATH OpenOpenAlexFDO

Authors N. Dadoun, David Kirkpatrick

Publication date 1989

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(89)90042-1

zbMATH Keywords

parallel algorithmsearchplanar graphsconvex polyhedraplanar subdivisionconvex hull of n points in \({\mathbb{R}}^ 3\)hierarchical subdivision searchlarge independent setsseparation of convex polyhedra

Mathematics Subject Classification ID

Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Planar graphs; geometric and topological aspects of graph theory (05C10) Polytopes and polyhedra (52Bxx)

Recommendations

• Parallel computational geometry
• Efficient parallel convex hull algorithms
• A sublogarithmic convex hull algorithm
• A time-optimal parallel algorithm for three-dimensional convex hulls
• THE PARALLEL 3D CONVEX HULL PROBLEM REVISITED

Cites work

• scientific article; zbMATH DE number 4047151 (Why is no real title available?)
• scientific article; zbMATH DE number 3778747 (Why is no real title available?)
• A batching method for coloring planar graphs
• A linear algorithm for determining the separation of convex polyhedra
• A new point-location algorithm and its practical efficiency: comparison with existing algorithms
• Convex hulls of finite sets of points in two and three dimensions
• Fast detection of polyhedral intersection
• Optimal Search in Planar Subdivisions
• Parallel algorithms for fractional and maximal independent sets in planar graphs
• Parallel computational geometry
• Parallel construction of subdivision hierarchies

Cited in

(13)

• Storing the subdivision of a polyhedral surface
• New parallel algorithms for convex hull and triangulation in 3-dimensional space
• The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs
• Optimal parallel algorithms on planar graphs
• A time-optimal parallel algorithm for three-dimensional convex hulls
• Optimal cooperative search in fractional cascaded data structures
• Parallel construction of subdivision hierarchies
• Optimal, output-sensitive algorithms for constructing planar hulls in parallel
• A parallel algorithm for constructing projection polyhedra
• Parallel construction of quadtrees and quality triangulations
• Parallel algorithms for fractional and maximal independent sets in planar graphs
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• Dynamic point location in arrangements of hyperplanes

This page was built for publication: Parallel construction of subdivision hierarchies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124347)