• Login
    View Item 
    •   Eurographics DL Home
    • Eurographics Workshops and Symposia
    • EGGH: SIGGRAPH/Eurographics Workshop on Graphics Hardware
    • EGGH87: Eurographics Workshop on Graphics Hardware 1987
    • View Item
    •   Eurographics DL Home
    • Eurographics Workshops and Symposia
    • EGGH: SIGGRAPH/Eurographics Workshop on Graphics Hardware
    • EGGH87: Eurographics Workshop on Graphics Hardware 1987
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    065-073.pdf (480.6Kb)
    Date
    1987
    Author
    Dévai, F.
    Pay-Per-View via TIB Hannover:

    Try if this item/paper is available.

    Metadata
    Show full item record
    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."
    BibTeX
    @inproceedings {10.2312:EGGH:EGGH87:065-073,
    booktitle = {Eurographics Workshop on Graphics Hardware},
    editor = {Fons Kuijk and Wolfgang Strasser},
    title = {{An O(log N) Parallel Time Exact Hidden-LineAlgorithm}},
    author = {Dévai, F.},
    year = {1987},
    publisher = {The Eurographics Association},
    ISSN = {1727-3471},
    ISBN = {3-540-50109-6},
    DOI = {10.2312/EGGH/EGGH87/065-073}
    }
    URI
    http://dx.doi.org/10.2312/EGGH/EGGH87/065-073
    Collections
    • EGGH87: Eurographics Workshop on Graphics Hardware 1987

    Eurographics Association copyright © 2013 - 2023 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA
     

     

    Browse

    All of Eurographics DLCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    BibTeX | TOC

    Create BibTeX Create Table of Contents

    Eurographics Association copyright © 2013 - 2023 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA