A faster optimal algorithm for the measure problem
| Autor: | Weixiong Zhang, Stephan Olariu, Zhaofang Wen |
|---|---|
| Rok vydání: | 1991 |
| Předmět: |
Computer Networks and Communications
Open problem Model of computation Parallel algorithm Computational geometry Binary logarithm Computer Graphics and Computer-Aided Design Theoretical Computer Science Combinatorics Set (abstract data type) Artificial Intelligence Hardware and Architecture Log-log plot TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Algorithm Software MathematicsofComputing_DISCRETEMATHEMATICS Mathematics Measure problem |
| Zdroj: | Parallel Computing. 17:683-687 |
| ISSN: | 0167-8191 |
| DOI: | 10.1016/s0167-8191(05)80058-4 |
| Popis: | The measure problem involves computing the area of the union of a set of n iso-oriented rectangles in the plane. Recently, it has been shown that for a set of n such rectangles, the measure problem can be solved in O(log n log log n) time, using O(n/log log n) processors in the CREW PRAM model of computation. In this note we show that the measure problem can be solved optimally in O(log n) time using O(n) processors in the same model of computation, thus settling an open problem posed in [8]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|