An optimal parallel algorithm for building a data structure for planar point location

Richard Cole; Ofer Zajlcek

doi:10.1016/0743-7315(90)90103-V

An optimal parallel algorithm for building a data structure for planar point location

Richard Cole, Ofer Zajlcek

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Using a modification of the Approximate Parallel Scheduling of R. Cole and U. Vishkin (SIAM J. Comput. 17, 11988),128-142), we give an optimal parallel algorithm for generating a linear size data structure for planar point location that supports an O(log n) query time. Our algorithm runs on a CREW PRAM in time O(log n) using n log n processors.

Original language	English (US)
Pages (from-to)	280-285
Number of pages	6
Journal	Journal of Parallel and Distributed Computing
Volume	8
Issue number	3
DOIs	https://doi.org/10.1016/0743-7315(90)90103-V
State	Published - Mar 1990

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Artificial Intelligence

Access to Document

10.1016/0743-7315(90)90103-V

Cite this

@article{0075a80a62c4431b9a5434262765665a,

title = "An optimal parallel algorithm for building a data structure for planar point location",

abstract = "Using a modification of the Approximate Parallel Scheduling of R. Cole and U. Vishkin (SIAM J. Comput. 17, 11988),128-142), we give an optimal parallel algorithm for generating a linear size data structure for planar point location that supports an O(log n) query time. Our algorithm runs on a CREW PRAM in time O(log n) using n log n processors.",

author = "Richard Cole and Ofer Zajlcek",

note = "Funding Information: * This research was supported in part by the NSF under Grants DCR-84-01633 and CCR-87-0227 1; the ONR under Grant N00014-85-K-0046; the Applied Mathematical Science subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract DE-ACOZ-76ER03077; and the John Simon Guggenheim Memorial Foundation.",

year = "1990",

month = mar,

doi = "10.1016/0743-7315(90)90103-V",

language = "English (US)",

volume = "8",

pages = "280--285",

journal = "Journal of Parallel and Distributed Computing",

issn = "0743-7315",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - An optimal parallel algorithm for building a data structure for planar point location

AU - Cole, Richard

AU - Zajlcek, Ofer

N1 - Funding Information: * This research was supported in part by the NSF under Grants DCR-84-01633 and CCR-87-0227 1; the ONR under Grant N00014-85-K-0046; the Applied Mathematical Science subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract DE-ACOZ-76ER03077; and the John Simon Guggenheim Memorial Foundation.

PY - 1990/3

Y1 - 1990/3

N2 - Using a modification of the Approximate Parallel Scheduling of R. Cole and U. Vishkin (SIAM J. Comput. 17, 11988),128-142), we give an optimal parallel algorithm for generating a linear size data structure for planar point location that supports an O(log n) query time. Our algorithm runs on a CREW PRAM in time O(log n) using n log n processors.

AB - Using a modification of the Approximate Parallel Scheduling of R. Cole and U. Vishkin (SIAM J. Comput. 17, 11988),128-142), we give an optimal parallel algorithm for generating a linear size data structure for planar point location that supports an O(log n) query time. Our algorithm runs on a CREW PRAM in time O(log n) using n log n processors.

UR - http://www.scopus.com/inward/record.url?scp=0025402346&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025402346&partnerID=8YFLogxK

U2 - 10.1016/0743-7315(90)90103-V

DO - 10.1016/0743-7315(90)90103-V

M3 - Article

AN - SCOPUS:0025402346

SN - 0743-7315

VL - 8

SP - 280

EP - 285

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 3

ER -

An optimal parallel algorithm for building a data structure for planar point location

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this