Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
Author:
- Dan E. WillardDWDan E. Willard
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 29 (3) , 1030-1049
Abstract
This article illustrates several examples of computer science problems whose performance can be improved with the use of either the fusion trees [Fredman and Willard, J. Comput. System Sci., 47 (1993), pp. 424--436; Fredman and Willard, J. Comput. System Sci., 48 (1994), pp. 533--551] or one of several recent improvements to this data structure. It is likely that many other data structures can also have their performance improved with fusion trees. The examples here are only illustrative.Keywords
This publication has 42 references indexed in Scilit:
- Fusion trees can be implemented with AC0 instructions onlyTheoretical Computer Science, 1999
- Dominators in Linear TimeSIAM Journal on Computing, 1999
- Sorting in Linear Time?Journal of Computer and System Sciences, 1998
- Improved Parallel Integer Sorting without Concurrent WritingInformation and Computation, 1997
- When Can We Sort ino(nlogn) Time?Journal of Computer and System Sciences, 1997
- Engineering a sort functionSoftware: Practice and Experience, 1993
- Lower bounds for orthogonal range searching: part II. The arithmetic modelJournal of the ACM, 1990
- Filtering Search: A New Approach to Query-AnsweringSIAM Journal on Computing, 1986
- Multidimensional divide-and-conquerCommunications of the ACM, 1980
- Efficient worst-case data structures for range searchingActa Informatica, 1980