Parallel batched planar point location on the CCC
type: Item
instance of: scholarly article
title: Parallel batched planar point location on the CCC
zbMATH Open document ID: 0689.68063
DOI: 10.1016/0020-0190(89)90137-3
author: Jianyong Qiao
author: Sumit K. Garg
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
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)\).
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 68U99
zbMATH DE Number: 4130015
zbMATH Keywords: point location
zbMATH Keywords: computational geometry
zbMATH Keywords: parallel computation
zbMATH Keywords: fixed interconnections
zbMATH Keywords: CREW PRAM
zbMATH Keywords: cube-connected-cycle (CCC) architecture
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90137-3
OpenAlex ID: W2071153521
cites work: A New Approach to Planar Point Location
description: scientific article; zbMATH DE number 4130015