## A Consistent Hierarchical Representation for Vector Data

Randal C. Nelson and Hanan Samet

Department of Computer Science

University of Rochester, University of Maryland

Rochester, NY 14627

**Abstract:**
A consistent hierarchical data structure for the representation of
vector data is presented.
It makes use of a concept termed a
*line segment fragment*
to prevent data degradation under splitting or clipping of vector
primitives.
This means that the insertion and subsequent deletion
(and vice versa) of a vector leaves the data unchanged.
Vectors are represented exactly and not as digital approximations.
The data is dynamically organized by use of simple probabilistic
splitting and merging rules.
The use of the structure for implementing a geographic information system
is described.
Algorithms for constructing and manipulating the structure are provided.
Results of empirical tests comparing the structure
to other representations in the literature are given.