Chapter 2 - Basic data structures

Summary

Data structures are the keystone on which all algorithmic techniques rely. The definition of basic yet high-level data structures, with precise features and a well-studied implementation, allows the designer of an algorithm to concentrate on the core issues of the problem. For the programmer, it saves the tedious task of creating and administrating each pointer.

Throughout this book, we describe data structures especially designed for representing geometric objects and dealing with them. But computational geometers also make extensive use of data structures that represent subsets or sequences of objects. These structures can be used directly by the algorithms, or modified and augmented for geometric use. The first part of this chapter recalls the terminology and features of each basic data structure used in this book. It is useful to know how these structures can be implemented and what their performances are. The most delicate problem is undoubtedly the one addressed by dictionaries and priority queues, which treat finite subsets of a totally ordered set (the universe). To achieve better efficiency, these structures are usually encoded as balanced binary trees. For instance, the second part of this chapter describes red-black trees, a class of balanced trees that can be used to implement dictionaries and priority queues. Finally, when the universe is finite, dictionaries and priority queues can be even more efficiently implemented by other more sophisticated techniques, the characteristics of which are given without proof in the third part of this chapter.