Parallel batched planar point location on the CCC

DOI10.1016/0020-0190(89)90137-3MaRDI QIDQ582096zbMATH OpenOpenAlexFDO

Authors Jianyong Qiao, Sumit K. Garg

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90137-3

zbMATH Keywords

computational geometryCREW PRAMcube-connected-cycle (CCC) architecturefixed interconnectionsparallel computationpoint location

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Computing methodologies and applications (68U99)

Review text

We consider the following problem, called ``batched planar point location: Given a planar subdivision R induced by a plane graph \(G=(V,E)\), with \(| V| =N\), and a set S of M points in the plane, we wish to locate in parallel S in R, i.e., for each point \(p\in S\), we wish to find the region of R containing p. We assume throughout that \(M=\Theta (N)\).

Recommendations

• PLANAR POINT LOCATION REVISITED
• scientific article; zbMATH DE number 4090792
• Parallel Transitive Closure and Point Location in Planar Structures
• A new point-location algorithm and its practical efficiency: comparison with existing algorithms
• Adaptive point location in planar convex subdivisions

Cites work

• A New Approach to Planar Point Location

Cited in

(5)

• Output-sensitive generation of the perspective view of isothetic parallelepipeds
• On the multisearching problem for hypercubes
• AN IMPROVED HYPERCUBE BOUND FOR MULTISEARCHING AND ITS APPLICATIONS
• A simplified technique for hidden-line elimination in terrains
• Maximum weight independent set of circular-arc graph and its application

This page was built for publication: Parallel batched planar point location on the CCC

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