An O(log N) Parallel Time Exact Hidden-LineAlgorithm

dc.contributor.authorDévai, F.en_US
dc.contributor.editorFons Kuijk and Wolfgang Strasseren_US
dc.date.accessioned2014-02-06T14:01:45Z
dc.date.available2014-02-06T14:01:45Z
dc.date.issued1987en_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.description.seriesinformationEurographics Workshop on Graphics Hardwareen_US
dc.identifier.isbn3-540-50109-6en_US
dc.identifier.issn1727-3471en_US
dc.identifier.urihttps://doi.org/10.2312/EGGH/EGGH87/065-073en_US
dc.publisherThe Eurographics Associationen_US
dc.titleAn O(log N) Parallel Time Exact Hidden-LineAlgorithmen_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
065-073.pdf
Size:
480.65 KB
Format:
Adobe Portable Document Format