Optimal, output-sensitive algorithms for constructing upper envelope of line segments in parallel

Neelima Gupta, Sumit Chopra, Sandeep Sen

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

Abstract

In this paper we focus on the problem of designing very fast parallel algorithms for constructing the upper envelope of straight-line segments that achieve the O(n logH) work-boundfor input size n and output size H. Our algorithms are designed for the arbitrary CRCW PRAM model. We first describe an O(log n ・ (logH + log log n)) time deterministic algorithm for the problem, that achieves O(n logH) work boundfor H = Ω(log n). We present a fast randomized algorithm that runs in expectedtime O(logH ・ log log n) with high probability andd oes O(n logH) work. For logH = Ω(log log n), we can achieve the running time of O(logH) while simultaneously keeping the work optimal. We also present a fast randomized algorithm that runs in ˜O(log n/ log k) time with nk processors, k > logΩ(1) n. The algorithms do not assume any input distribution andthe running times holdwith high probability.

Original languageEnglish (US)
Title of host publicationFST TCS 2001
Subtitle of host publicationFoundations of Software Technology and Theoretical Computer Science - 21st Conference, Proceedings
EditorsRamesh Hariharan, V. Vinay, Madhavan Mukund
PublisherSpringer Verlag
Pages183-194
Number of pages12
ISBN (Print)3540430024
DOIs
StatePublished - 2001
Event21st Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS 2001 - Bangalore, India
Duration: Dec 13 2001Dec 15 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2245
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS 2001
Country/TerritoryIndia
CityBangalore
Period12/13/0112/15/01

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Optimal, output-sensitive algorithms for constructing upper envelope of line segments in parallel'. Together they form a unique fingerprint.

Cite this