O(log logn)-time integer geometry on the CRCW PRAM |
| |
Authors: | B. S. Chlebus K. Diks M. Kowaluk |
| |
Affiliation: | (1) Instytut Informatyki, Universytet Warszawski, Banacha 2, 02-097, Warszawa, Poland |
| |
Abstract: | We study problems in computational geometry on PRAMs under the assumption that input objects are specified by points withO(logn)-bit coordinates, or, equivalently, with polynomially bounded integer coordinates. We show that in this setting many geometric problems can be solved in time O(log logn). The following five specific problems are investigated:closest pair of points, intersection of convex polygons, intersection of manhattan line segments, dominating set, andlargest empty square. Algorithms solving them are developed which operate in time O(log logn) on the arbitrary CRCW PRAM. The number of processors used is eitherO(n) orO(n logn).This research was supported in part by Grants KBN 2-2044-92-03, KBN 2-2043-92-03, and KBN 2-1190-91-01. |
| |
Keywords: | PRAM Computational geometry Highly parallelizable problems |
本文献已被 SpringerLink 等数据库收录! |
|