Parallel construction of subdivision hierarchies

DOI10.1016/0022-0000(89)90042-1zbMath0678.68056OpenAlexW2014495691MaRDI QIDQ1124347

N. Dadoun, David G. 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

planar graphsparallel algorithmsearchconvex polyhedraplanar subdivisionconvex hull of n points in \({\mathbb{R}}^ 3\)hierarchical subdivision searchlarge independent setsseparation of convex polyhedra

Mathematics Subject Classification ID

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

Related Items

A time-optimal parallel algorithm for three-dimensional convex hulls, Optimal cooperative search in fractional cascaded data structures, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Parallel construction of subdivision hierarchies, 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, Parallel algorithms for fractional and maximal independent sets in planar graphs, Dynamic point location in arrangements of hyperplanes, Optimal parallel algorithms on planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Fast detection of polyhedral intersection
• Parallel algorithms for fractional and maximal independent sets in planar graphs
• Parallel computational geometry
• Parallel construction of subdivision hierarchies
• 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
• Optimal Search in Planar Subdivisions
• Convex hulls of finite sets of points in two and three dimensions