Parallel Transitive Closure and Point Location in Planar Structures

DOI10.1137/0220045zbMath0736.68037OpenAlexW2056711744MaRDI QIDQ3978176

Roberto Tamassia, Jeffrey Scott Vitter

Publication date: 25 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1808/7171

zbMATH Keywords

reachabilityvisibilitygraph drawingfractional cascadingplanar point locationplanar \(st\)-graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)

Related Items (10)

Selecting distances in the plane ⋮ An efficient parallel algorithm for finding rectangular duals of plane triangular graphs ⋮ An efficient parallel algorithm for shortest paths in planar layered digraphs ⋮ A time-optimal parallel algorithm for three-dimensional convex hulls ⋮ Optimal cooperative search in fractional cascaded data structures ⋮ Designing checkers for programs that run in parallel ⋮ Approximating nearest neighbor among triangles in convex position ⋮ A near-linear algorithm for the planar segment-center problem ⋮ Bipolar orientations revisited ⋮ Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

This page was built for publication: Parallel Transitive Closure and Point Location in Planar Structures