dc.contributor.author Dévai, F. en_US dc.contributor.editor Fons Kuijk and Wolfgang Strasser en_US dc.date.accessioned 2014-02-06T14:01:45Z dc.date.available 2014-02-06T14:01:45Z dc.date.issued 1987 en_US dc.identifier.isbn 3-540-50109-6 en_US dc.identifier.issn 1727-3471 en_US dc.identifier.uri http://dx.doi.org/10.2312/EGGH/EGGH87/065-073 en_US dc.description.abstract "Parallel algorithms are given for the exact solution of the hidden-line problem. Most of the parallel algorithms proposed for visibility problems in the literature give approximate solutions. and thus cannot yield an upper bound on the complexity of the particular problem. The first algorithm proposed here is worth mentioning not only for its simplicity. but also from a practical point of view: a speed up of a factor P is achieved by using P processors. l"";;P"";;N. where N is the number of edges used to describe a polygonal scene. Additionally. the problem of aliasing inherent with approximation methods is avoided.The significance of the second algorithm, which is based on the first one, is mainly on the theoretical level: it is used to establish the parallel complexity of the hidden-line problem. The sequential complexity of this problem has recently been proved to be e(N2). and now we can prove that in the parallel case the problem is in the complexity class NC, Le., it can be solved in time polynomial in logN by using a number of processors polynomial in N, assuming any reasonable model of parallel computation. More particularly, an O(logN) parallel time solution is given which cannot be further improved even if arbitrarily many processors of a concurrent read, exclusive write parallel RAM model are available." en_US dc.publisher The Eurographics Association en_US dc.title An O(log N) Parallel Time Exact Hidden-LineAlgorithm en_US dc.description.seriesinformation Eurographics Workshop on Graphics Hardware en_US
﻿