196 research outputs found
Space reduction and an extension for a hidden line elimination algorithm
No full textAbstractA simple intersection sensitive algorithm for the hidden line elimination problem, was presented by Nurmi in 1985. This algorithm has O((n + I) logn) time and space complexities, where n is the number of edges in the input scene and I is the number of their intersections on the projection plane. We describe a method that reduces the space requirements of the algorithm to O(n) while retaining the time complexity of O((n+I) logn). Furthermore we show that the algorithm can be easily extended to handle the more general problem of hidden surface removal
AND
No full textAbstract. A new data structure called interpolation search tree (1ST) is presented which supports interpolation search and insertions and deletions. Amortized insertion and deletion cost is O(log n). The expected search time in a random file is O(log log n). This is not only true for the uniform distribution but for a wide class of probability distributions. Categories and Subject Descriptors: E. 1 [Data Structures]: trees; F.2 [Analysis of Algorithms an
- …
