Optimal parallel algorithms for polygon and point-set problems (Preliminary Version)

Richard Cole, Michael T. Goodrich

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we give parallel algorithms for a number of problems defined on polygons and point sets. All of our algorithms have optimal T(n) P(n) products, where T(n) is the time complexity and P(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. In addition, our algorithms provide parallel analogues to well known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently that point-set problems, and that one can solve nearest-neighbor problems without explicitly constructing a Voronoi diagram.

Original languageEnglish (US)
Title of host publicationProceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988
PublisherAssociation for Computing Machinery, Inc
Pages201-210
Number of pages10
ISBN (Electronic)0897912705, 9780897912709
DOIs
StatePublished - Jan 6 1988
Event4th Annual Symposium on Computational Geometry, SCG 1988 - Urbana-Champaign, United States
Duration: Jun 6 1988Jun 8 1988

Publication series

NameProceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

Other

Other4th Annual Symposium on Computational Geometry, SCG 1988
CountryUnited States
CityUrbana-Champaign
Period6/6/886/8/88

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint Dive into the research topics of 'Optimal parallel algorithms for polygon and point-set problems (Preliminary Version)'. Together they form a unique fingerprint.

Cite this