`
`
`
`The Design and
`
`
`Analysis of
`
`Spatial Data
`
`Structures
`
`
`
`Page 1 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 1 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`
`
`
`
`The Design and
`
`
`Analysis of
`
`Spatial Data
`
`Structures
`
`
`
`
`Hanan Samet
`
`
`
`
`
`UNIVERSITY OF MARYLAND
`
`
`
`
`
`
`
`
`
`
`
`A
`VV
`
`
`
`
`ADDISON — WESLEY PUBLISHING COMPANY, INC.
`
`
`
`
`
`
`
`Reading, Massachusetts ° Menlo Park, California ° New York
`
`
`
`
`
`
`Don Mills, Ontario 0 Wokingham, England 0 Amsterdam
`
`
`
`
`
`
`
`Bonn 0 Sydney 0 Singapore 0 Tokyo 0 Madrid 0 San Juan
`
`
`
`Page 2 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 2 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`
`
`
`
`
`
`
`
`
`This book is in the Addison -Wesley Series in Computer Science
`
`
`
`
`
`Michael A. Harrison: Consulting Editor
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Many of the designations used by manufacturers and sellers to distinguish their products are claimed as
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark
`
`
`
`
`
`
`
`
`
`
`
`
`claim, the designations have been printed in initial caps or all caps.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The programs and applications presented in this book have been included for their instructional value.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`They have been tested with care, but are not guaranteed for any particular purpose. The publisher does not
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`offer any warranties or representations, nor does it accept any liabilities with respect to the programs or
`
`applications.
`
`
`
`
`
`Library of Congress Cataloging-in-Publication Data
`
`
`
`Samet, Hanan.
`
`
`
`
`
`
`
`
`
`
`
`The Design and analysis of spatial data structures/by Hanan Samet.
`p.
`cm.
`
`
`
`
`Bibliography: p.
`Includes index.
`
`
`ISBN 0—201—50255—0
`
`
`
`
`
`
`1. Data structures (Computer science)
`I. Title.
`
`
`QA76.9.D35826
`005.7'3 —dc19
`
`
`
`
`1989
`
`
`
`
`
`
`
`2. Computer graphics.
`
`
`
`
`
`89—30382
`CIP
`
`
`
`
`
`
`
`
`Reprinted with corrections January, 1994
`
`
`
`
`
`
`
`
`
`
`Copyright © 1990 by Addison-Wesley Publishing Company, Inc.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmit—
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`prior written permission of the publisher. Printed in the United States of America. Published simultane-
`
`
`
`ously in Canada.
`
`
`456789 1011 12 13 14—MA-97 9695 94
`
`
`
`
`
`
`
`
`
`
`
`Credits:
`
`Thor Bestul created the cover art.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Gyun' Fekete generated Figure 1.16; Daniel DeMenthon, Figures 120, 1.21, and 1.23; Jiang-Hsing
`
`
`
`
`
`
`
`
`
`
`
`
`Chu, Figures 2.48 and 2.52; and Walid Aref, Figures 4.38 through 4.40.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figures 1.1, 4.9, and 4.10 are from H. Samet and R. E. Webber, On encoding boundaries with quad-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`trees, IEEE Transactions on Pattern Analysis and Machine Intelligence 6, 3 (May 1984), 365—369. © 1984
`
`
`
`
`
`
`IEEE. Reprinted by permission of IEEE.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figures 1.2, 1.3, 1.5 through 1.10, 1.12, 1.14, 1.25, 1.26, 2.3, 2.4, 2.18, 2.20, 2.30, 2.32, 2.53, 2.54,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2.57, 2.58, 3.20, 3.21, 4.1 through 4.5, 4.7, 4.8, 4.11, and 5.2 are from H. Samet, The quadtree and related
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`hierarchical data structures, ACM Computing Surveys 16, 2 (June 1984), 187—260. Reprinted by permission
`of ACM.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figures 1.4 and 5.6 are from H. Samet and R. E. Webber, Hierarchical data structures and algorithms
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`for computer graphics. Part 1. Fundamentals, IEEE Computer Graphics and Applications 8, 3 (May 1988),
`
`
`
`
`
`
`
`
`
`48—68. © 1988 IEEE. Reprinted by permission of IEEE.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 1.30 is from M. Li, W. I. Grosky, and R. Jain, Normalized quadtrees with respect to transla-
`
`
`
`
`
`
`
`
`
`
`
`
`
`tions, Computer Graphics and Image Processing 20, 1 (September 1982), 72—81. Reprinted by permission
`of Academic Press.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`. Figures 2.7 and 2.10 through 2.15 are from H. Samet, Deletion in two-dimensional quad trees, Com-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`munications of the ACM 23, 12 (December 1980), 703—7 10. Reprinted by permission of ACM.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figures 2.26 and 2.27 are from D. T. Lee and C. K. Wong, Worst-case analysis for region and partial
`
`
`
`
`
`
`
`
`
`
`
`
`
`region searches in multidimensional binary search trees and quad trees, Acta Informatica 9. 1 (1977). 23—29-
`
`
`
`
`
`
`
`
`Reprinted by permrssron of Springer Verlag.
`
`
`
`
`Continued on p. 493
`
`
`
`
`
`
`Page 3 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 3 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`
`
`
`
`
`To my parents, Julius and Lotte
`
`
`
`Page 4 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 4 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`
`PREFACE
`
`
`
`
`
`
`
`
`
`
`
`
`
`Spatial data consist of points, lines, rectangles, regions, surfaces, and volumes. The
`
`
`
`
`
`
`
`
`
`
`
`representation of such data is becoming increasingly important
`in applications in
`
`
`
`
`
`
`
`
`computer graphics, computer vision, database management systems, computer-aided
`
`
`
`
`
`
`
`
`
`design, solid modeling, robotics, geographic information systems (GIS), image pro-
`
`
`
`
`
`
`
`
`
`
`cessing, computational geometry, pattern recognition, and other areas. Once an appli-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`cation has been specified, it is common for the spatial data types to be more precise.
`
`
`
`
`
`
`
`
`
`
`
`
`
`For example, consider a geographic information system (GIS).
`In such a case, line
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`data are differentiated on the basis of whether the lines are isolated (e.g., earthquake
`
`
`
`
`
`
`
`
`
`
`
`
`faults), elements of tree-like structures (e.g., rivers and their tributaries), or elements
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`of networks (e.g., rail and highway systems). Similarly region data are often in the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`form of polygons that are isolated (e.g., lakes), adjacent (e.g., nations), or nested (e.g.,
`
`
`
`
`
`
`contours). Clearly the variations are large.
`
`
`
`
`
`
`
`
`
`
`
`
`Many of the data structures currently used to represent spatial data are hierarchi—
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`cal. They are based on the principle of recursive decomposition (similar to divide and
`
`
`
`
`
`
`
`
`
`
`
`
`
`conquer methods [Aho74]). One such data structure is the quadtree (octree in three
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`dimensions). As we shall see, the term quadtree has taken on a generic meaning.
`In
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`this book, it is my goal to show how a number of hierarchical data structures used in
`
`
`
`
`
`
`
`
`
`
`
`
`different domains are related to each other and to quadtrees. My presentation concen-
`
`
`
`
`
`
`
`
`
`
`
`
`trates on these different representations and illustrates how a number of basic opera-
`
`
`
`
`
`
`tions that use them are performed.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Hierarchical data structures are useful because of their ability to focus on the
`
`
`
`
`
`
`
`
`
`
`
`
`
`interesting subsets of the data. This focusing results in an efficient representation and
`
`
`
`
`
`
`
`
`
`
`
`
`in improved execution times. Thus they are particularly convenient for performing set
`
`
`
`
`
`
`
`
`
`
`
`
`
`operations. Many of the operations described can often be performed as efficiently, or
`
`
`
`
`
`
`
`
`
`
`
`more so, with other data structures. Nevertheless hierarchical data structures are
`
`
`
`
`
`
`
`
`
`
`
`
`attractive because of their conceptual clarity and ease of implementation.
`In addition,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the use of some of them provides a spatial index. This is very useful in applications
`
`
`
`involving spatial databases.
`
`Page 5 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 5 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`
`viii
`
`
`n
`
`PREFACE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`As an example of the type of problems to which the techniques described in this
`
`
`
`
`
`
`
`
`
`
`
`book are applicable, consider a cartographic database consisting of a number of maps
`
`
`
`
`
`
`
`
`
`
`
`
`
`and some typical queries. The database contains a contour map, say at 50-foot eleva-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion intervals, and a land use map classifying areas according to crop growth. Our
`
`
`
`
`
`
`
`
`
`
`
`
`goal is to determine all regions between 400- and 600-foot elevation levels where
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`wheat is grown. This will require an intersection operation on the tWO maps. Such an
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`analysis could be rather costly, depending on the way the maps are represented. For
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`example, since areas where Corn is grown are of no interest, we wish to spend a
`
`
`
`
`
`
`
`
`
`
`minimal amount of effort searching such regions. Yet traditional region representa-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tions such as the boundary code [Free74] are very local
`in application, making it
`
`
`
`
`
`
`
`
`
`
`
`
`difficult to avoid examining a com-growing area that meets the desired elevation
`
`
`
`
`
`
`
`
`
`
`
`criterion.
`In contrast, hierarchical representations such as the region quadtree are
`
`
`
`
`
`
`
`
`
`
`
`
`
`more global in nature and enable the elimination of larger areas from consideration.
`
`
`
`
`
`
`
`
`
`
`
`
`Another query might be to determine whether two roads intersect within a given
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`area. We could check them point by point; however, a more efficient method of
`
`
`
`
`
`
`
`
`
`
`
`
`
`analysis would be to represent them by a hierarchical sequence of enclosing rectangles
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and to discover whether in fact the rectangles do overlap. If they do not, the search is
`
`
`
`
`
`
`
`
`
`
`
`
`
`terminated. If an intersection is possible, more work may have to be done, depending
`
`
`
`
`
`
`
`on which method of representation is used.
`
`
`
`
`
`
`
`
`
`
`
`
`A similar query can be constructed for point data—for example, to determine
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`all cities within 50 miles of St. Louis that have a population in excess of 20,000.
`
`
`
`
`
`
`
`
`
`
`
`
`Again we could check each city individually. However, using a representation that
`
`
`
`
`
`
`
`
`
`
`
`
`
`decomposes the United States into square areas having sides of length 100 miles
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`would mean that at most four squares need to be examined. Thus California and its
`
`
`
`
`
`
`adjacent states can be safely ignored.
`
`
`
`
`
`
`
`
`
`
`
`
`Finally, suppose we wish to integrate our queries over a database containing
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`many different types of data (e.g., points, lines, areas). A typical query might be,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`“Find all cities with a population in excess of 5,000 people in wheat-growing regions
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`within 20 miles of the Mississippi River.” In this book we will present a number of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`different ways of representing data so that such queries and other operations can be
`
`
`efficiently processed.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`This book is organized as follows. There is one chapter for each spatial data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`type, in which I present a number of different data structures. The aim is to gain the
`
`
`
`
`
`
`
`
`
`
`
`
`
`ability to evaluate them and to determine their applicability. Two problems are treated
`
`
`
`
`
`
`
`
`
`
`
`
`
`in great detail:
`the rectangle intersection problem, discussed in the context of the
`
`
`
`
`
`
`
`
`
`
`
`
`representation of collections of small rectangles (Chapter 3), and the point location
`
`
`
`
`
`
`
`
`
`
`
`
`
`problem, discussed in the context of the representation of curvilinear data (Chapter 4).
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`A comprehensive treatment of the use of quadtrees and octrees in other applications in
`
`
`
`
`
`
`
`
`
`
`computer graphics, image processing, and geographic information systems (GIS) can
`
`
`
`
`be found in [Same90b].
`
`
`
`
`
`
`
`
`
`
`
`Chapter 1 gives a general introduction to the principle of recursive decomposi-
`
`
`
`
`
`
`
`
`
`
`
`
`tion with a concentration on two-dimensional regions. Key properties, as well as a
`
`
`
`
`historical overview, are presented.
`
`
`
`Page 6 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 6 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`
`PREFACE
`
`
`II
`
`iX
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Chapter 2 discusses hierarchical representations of multidimensional point data.
`
`
`
`
`
`
`
`
`
`
`
`These data structures are particularly useful in applications in database management
`
`
`
`
`
`
`
`
`
`
`
`systems because they are designed to facilitate responses to search queries.
`
`
`
`
`
`
`
`
`
`
`Chapter 3 examines the hierarchical representation of collections of small rec-
`
`
`
`
`
`
`
`
`
`
`
`tangles. Such data arise in applications in Computational geometry, very large-scale
`
`
`
`
`
`
`
`
`
`integrations (VLSI), cartography, and database management. Examples from these
`
`
`
`
`
`
`
`
`
`
`
`
`fields (e.g., the rectangle intersection problem) are used to illustrate their differences.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Many of the representations are closely related to those used for point data. This
`
`
`
`
`
`
`chapter is an expansion of [Same88a].
`
`
`
`
`
`
`
`
`
`
`Chapter 4 treats the hierarchical representation of curvilinear data. The primary
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`focus is on the representation of polygonal maps. The goal is to be able to Solvethe
`
`
`
`
`
`
`
`
`
`
`point location problem. Quadtree-like solutions are compared with those from Com-
`
`
`
`
`
`
`
`
`
`
`
`
`putational geometry such as the K-structure [Kirk83] and the layered dag [Edel86a].
`
`
`
`
`
`
`
`
`
`
`
`Chapter 5 looks at the representation of three-dimensional region data.
`In this
`
`
`
`
`
`
`
`
`
`
`
`
`
`case, a number of octree variants are examined, as well as constructive solid geometry
`
`
`
`
`
`
`
`
`
`
`(CSG) and the boundary model
`(BRep). Algorithms are discussed for converting
`
`
`
`
`
`
`
`
`
`
`between some of these representations. The representation of surfaces (i.e., 2.5-
`
`
`
`
`
`
`
`
`
`dimensional data) is also briefly discussed in this chapter.
`
`
`
`
`
`
`
`
`
`
`
`
`There are a number of topics for which justice requires a considerably more
`
`
`
`
`
`
`
`
`
`
`
`detailed treatment. However, due to space limitations, I have omitted a detailed dis-
`
`
`
`
`
`
`
`
`
`
`
`
`
`cussion of them and instead refer interested readers to the appropriate literature. For
`
`
`
`
`
`
`
`
`
`
`example, surface representations are discussed briefly with three-dimensional data in
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Chapter 5 (also see Chapter 7 of [Same90b]). The notion of a pyramid is presented
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`only at a cursory level in Chapter 1 so that it can be contrasted with the quadtree.
`In
`
`
`
`
`
`
`
`
`
`
`
`
`particular, the pyramid is a multiresolution representation, whereas the quadtree is a
`
`
`
`
`
`
`
`
`
`
`variable resolution representation. Readers are referred to Tanimoto and Klinger
`
`
`
`
`
`
`
`
`
`
`
`
`
`[Tani80] and the Collection of papers edited by Rosenfeld [Rose83a] for a more
`
`
`
`
`comprehensive exposition on pyramids.
`
`
`
`
`
`
`
`
`
`
`Results from computational geometry, although related to many of the topics
`
`
`
`
`
`
`
`
`
`
`
`
`
`covered in this book, are discussed only in the context of representations for collec-
`
`
`
`
`
`
`
`
`
`
`
`
`
`tions of small rectangles (Chapter 3) and curvilinear data (Chapter 4). For more
`
`
`
`
`
`
`
`
`
`
`
`
`
`details on early work involving Some of these and related topics, interested readers
`
`
`
`
`
`
`
`
`
`
`
`should consult the surveys by Bentley and Friedman [Bent79b], Overmars [Over88a],
`
`
`
`
`
`
`
`
`
`Edelsbrunner [Edel84], Nagy and Wagle [Nagy79], Peuquet [Peuq84], Requicha
`
`
`
`
`
`
`
`
`
`[Requ80], Srihari
`[Srih81],‘ Samet and Rosenfeld [Same80d], Samet
`[Same84b,
`
`
`
`
`
`
`
`
`
`Same88a], Samet and Webber [Same88c, Same88d], and Toussaint [Tous80].
`
`
`
`
`
`
`
`
`
`
`
`
`There are aISO a number of excellent texts containing material related to the
`
`
`
`
`
`
`
`
`
`
`
`
`topics that I cover. Rosenfeld and Kak [Rose82a] should be consulted for an ency-
`
`
`
`
`
`
`
`
`
`
`clopedic treatment of image processing. Mantyla [Mant87] has written a comprehen-
`
`
`
`
`
`
`
`
`
`
`
`sive introduction to solid modeling. Burrough [Burr86] provides a survey of geo-
`
`
`
`
`
`
`
`
`
`
`graphic information systems (GIS). Overmars [Over83] has produced a particularly
`
`
`
`
`
`
`
`
`
`
`
`
`good treatment of multidimensional point data.
`In a similar vein, see Mehlhom’s
`
`
`
`
`
`
`
`
`[Mehl84] unified treatment of multidimensional
`searching and computational
`
`
`
`
`
`
`
`
`
`
`geometry. For thorough introductions to computational geometry, see Preparata and
`
`
`
`
`
`Page 7 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 7 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`PREFACE
`
`
`
`
`ii
`
`xiii
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`K-structure and the layered dag in Section 4.3 are relevant to computational geometry.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bucket methods such as linear hashing, spiral hashing. grid file. and EXCELL. in Sec-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion 2.8, and R-trees in Section 3.5.3 are important in the study of database manage-
`
`
`
`
`
`
`
`
`
`
`ment systems. Methods for multidimensional searching that are discussed include k—d
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`trees in Section 2.4, range trees and priority search trees in Section 2.5, and point-
`
`
`
`
`
`
`
`
`
`
`based rectangle representations in Section 3.4. The discussions of the representation
`
`
`
`
`
`
`
`
`
`
`
`of two-dimensional regions in Chapter 1. polygonal representations in Chapter 4, and
`
`
`
`
`
`
`
`
`
`
`
`
`
`use of point methods for focussing the Hough Transform are relevant to image pro-
`
`
`
`
`
`
`
`
`cessing. Finally the rectangle-representation methods and plane-sweep methods of
`
`
`
`
`
`
`
`
`
`Chapter 3 are important in the field of VLSI design.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The natural home for courses that use this book is in a Computer science depart-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ment, but the book Could also be used in a curriculum in geographic information
`
`
`
`
`
`
`
`
`
`
`
`
`
`systems (615). Such a course is offered in geography departments. The emphasis for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a course in this area would be on the use of quadtree-like methods for representing
`
`
`spatial data.
`
`
`
`
`
`
`
`
`Page 8 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 8 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`x
`
`
`
`
`II
`
`PREFACE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Shamos [Prep85] and Edelsbrunner [Ede187] (also see [Prep83, ORou88]). A broader
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`view of the literature can be found in related bibliographies such as the ongoing col-
`
`
`
`
`
`
`
`
`
`lective effort coordinated by Edelsbrunner [Ede183c, Ede188], and Rosenfeld’s annual
`
`
`
`
`
`
`
`
`
`
`
`collection of references in the journal Computer Vision, Graphics, and Image Pro-
`
`
`
`cessing (e.g., [Rose88]).
`
`
`
`
`
`
`
`
`
`
`
`
`Nevertheless, given the broad and rapidly expanding nature of the field, I am
`
`
`
`
`
`
`
`
`
`
`
`
`bound to have omitted significant concepts and references.
`In addition at times I
`
`
`
`
`
`
`
`
`
`
`
`
`
`devote a disproportionate amount of attention to some concepts at the expense of oth-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ers. This is principally for expository purposes; I feel that it is better to understand
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`some structures well rather than to give readers a quick runthrough of buzzwords. For
`
`
`
`
`
`
`
`
`
`
`
`
`these indiscretions, I beg your pardon and hope you nevertheless bear with me.
`
`
`
`
`
`
`
`
`
`
`
`
`My approach is an algorithmic one. Whenever possible, I have tried to motivate
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`critical steps in the algorithms by a liberal use of examples.
`I feel
`that
`it
`is of
`
`
`
`
`
`
`
`
`
`
`
`
`
`paramount importance for readers to see the ease with which the representations can
`
`
`
`
`
`
`
`
`
`
`
`
`
`be implemented and used.
`In each chapter, except for the introduction (Chapter 1), I
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`give at least one detailed algorithm using pseudo-code so that readers can see how the
`
`
`
`
`
`
`
`
`
`
`
`
`
`ideas can be applied. The pseudo-code is a variant of the ALGOL [Naur60] program-
`
`
`
`
`
`
`
`
`
`
`
`
`ming language that has a data structuring facility incorporating pointers and record
`
`
`
`
`
`
`
`
`
`
`
`
`structures. Recursion is used heavily. This language has similarities to C [Kem78],
`
`
`
`
`
`
`
`
`
`
`
`
`PASCAL [Jens74], SAIL [Reis76], and ALGOL W [Baue68].
`Its basic features are
`
`
`
`
`
`
`
`
`
`
`
`
`
`described in the Appendix. However, the actual code is not crucial to understanding
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the techniques, and it may be skipped on a first reading. The index indicates the page
`
`
`
`
`
`
`
`
`
`numbers where the code for each algorithm is found.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`In many cases I also give an analysis of the space and time requirements of dif-
`
`
`
`
`
`
`
`
`
`
`
`
`
`ferent data structures and algorithms. The analysis is usually of an asymptotic nature
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and is in terms of big 0 and Q notation [Knut76]. The big 0 notation denotes an
`
`
`
`
`
`
`
`
`
`
`
`
`
`upper bound. For example, if an algorithm takes 0(log2N) time, then its worst-case
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`behavior is never any worse than log2N. The Q notation denotes a lower bound. As
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`an example of its use, consider the problem of sorting N numbers. When we say that
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`sorting is Q(N-log2N) we mean that given any algorithm for sorting, there is some set
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ofN input values for which the algorithm will require at least this much time.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`At times I also describe implementations of some of the data structures for the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`purpose of comparison.
`In such cases counts, such as the number of fields in a record,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`are often given. These numbers are meant only to amplify the discussion. They are
`
`
`
`
`
`
`
`
`
`
`
`
`
`not to be taken literally. as improvements are always possible once a specific applica-
`
`
`
`
`
`tion is analyzed more carefully.
`
`
`
`
`
`
`
`
`
`
`
`Each chapter contains a substantial number of exercises. Many of the exercises
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`develop further the material in the text as a means of testing the reader’s understand-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ing, as well as suggesting future directions. When the exercise or its solution is not
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`my own, I have preceded it with the name of its originator. The exercises have not
`
`
`
`
`
`
`
`
`
`
`
`
`been graded by difficulty. They rarely require any mathematical skills beyond the
`
`
`
`
`
`
`
`
`
`
`
`
`
`undergraduate level for their solution. However, while some of the exercises are quite
`
`
`
`
`
`
`
`
`
`
`
`straightforward, others require some ingenuity. Solutions, or references to papers that
`
`
`
`
`
`
`Page 9 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 9 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`
`PREFACE
`
`
`H
`
`
`Xi
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`contain the Solution, are provided for a substantial number of the exercises that do not
`
`
`
`
`
`
`
`
`
`
`
`
`require programming. Readers are cautioned to try to solve the exercises before tum-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ing to the solutions.
`It is my belief that much can be learned this way (for the student
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and, even more so, for the author). The motivation for undertaking this task was my
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`wonderful experience on my first encounter with the rich work on data structures by
`
`
`
`Knuth [Knut73a, Knut73b].
`
`
`
`
`
`
`
`
`
`
`
`
`An extensive bibliography is provided. It contains entries for both this book and
`
`
`
`
`
`
`
`
`
`
`
`
`
`the companion text [Same90b]. Not all of the references that appear in the bibliogra-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`phy are cited in the two texts. They are retained for the purpose of giving readers the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ability to access the entire body of literature relevant to the topics discussed in them.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Each reference is annotated with a key word(s) and a list of the numbers of the sec-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tions in which it is cited in either of the texts (including exercises and solutions).
`In
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`addition, a name and credit index is provided that indicates the page numbers in this
`
`
`
`
`
`
`
`
`
`
`
`
`book on which each author’s work is cited or a credit is made.
`
`
`
`
`
`
`ACKNOWLEDGMENTS
`
`
`
`me.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Over the years I have received help from many people, and I am extremely
`
`
`
`
`
`
`
`
`
`
`
`
`
`grateful to them.
`In particular Robert E. Webber, Markku Tamminen, and Michael B.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Dillencourt have generously given me much of their time and have gone over critical
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`parts of the book.
`I have drawn heavily on their knowledge of some of the topics
`
`
`
`
`
`
`
`
`
`
`
`
`
`covered here.
`I have also been extremely fortunate to work with Azriel Rosenfeld
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`over the past ten years. His dedication and scholarship have been a true inspiration to
`
`
`
`
`
`
`I deeply cherish our association.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`I was introduced to the field of spatial data structures by Gary D. Knott who
`
`
`
`
`
`
`
`
`
`
`
`
`
`asked “how to delete in point quadtrees.” Azriel Rosenfeld and Charles R. Dyer pro-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`vided much interaction in the initial phase of my research. Those discussions led to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the discovery of the neighbor-finding principle. It is during that time that many of the
`
`
`
`
`
`
`
`
`
`
`basic conversion algorithms between quadtrees and other image representations were
`
`
`
`
`
`
`
`
`
`
`
`
`
`developed as well.
`I learned much about image processing and computer vision from
`
`
`
`
`
`
`
`
`
`
`
`
`them. Robert E. Webber taught me computer graphics, Markku Tarnminen taught me
`
`
`
`
`
`
`
`
`
`
`
`solid modeling and representations for multiattribute data, and Michael B. Dillencour'
`
`
`
`
`
`taught me about computational geometry.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`During the time that this book was written, my research was supported, in part.
`
`
`
`
`
`
`
`
`
`
`
`by the National Science Foundation,
`the Defense Mapping Agency,
`the Harry
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Diamond Laboratory, and the Bureau of the Census.
`In particular I would like tn
`
`
`
`
`
`
`
`
`
`
`
`
`
`thank Richard Antony, Y. T. Chien, Su-shing Chen, Hank Cook, Phil Emmerrnan, In»:
`
`
`
`
`
`
`
`
`
`
`
`
`Rastatter, Alan Saalfeld, and Larry Tokarcik.
`I am appreciative of their support.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Many people helped me in the process of preparing the book for publication
`
`
`
`
`
`
`
`
`
`
`Acknowledgments are due to Rene McDonald for Coordinating the day-to—day matter:
`
`
`
`
`
`Page 10 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 10 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`Xil
`
`
`
`H
`
`PREFACE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`of getting the book out and copyediting; to Scott Carson, Emery Jou, and Jim Purtilo
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`for TROFF assistance beyond the call of duty; to Marisa Antoy and Sergio Antoy for
`
`
`
`
`
`
`
`
`
`
`
`
`designing and implementing the algorithm forrnatter used to typeset the algorithms; to
`
`
`
`
`
`
`
`
`
`
`
`
`
`Barbara Burnett, Michael B. Dillencourt, and Sandra German for help with the index;
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`to Jay Weber for setting up the TROFF macrofiles so that I can keep track of symbolic
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`names and thus be able to move text around without worrying about the numbering of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`exercises, sections, and chapters; to Liz Allen for early TROFF help; to Nono Kusuma,
`
`
`
`
`
`
`
`
`
`
`
`
`
`Mark Stanley, and Joan Wright Hamilton for drawing the figures; to Richard Muntz
`
`
`
`
`
`
`
`
`
`
`
`
`
`and Gerald Estrin for providing temporary office space and computer access at UCLA;
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`to Sandy German, Gwen Nelson, and Janet Salzman for help in initial typing of the
`
`
`
`
`
`
`
`
`
`
`
`
`
`manuscript;
`to S. S. Iyengar, Duane Marble, George Nagy, and Terry Smith who
`
`
`
`
`
`
`
`
`
`
`
`
`
`reviewed the book; and to Peter Gordon, John Remington, and Keith Wollman at
`
`
`
`
`
`
`
`
`
`
`Addison-Wesley Publishing Company for their encouragement and confidence in this
`
`project.
`
`
`
`
`
`
`
`
`
`
`Aside from the individuals named above, I have also benefited from discussions
`
`
`
`
`
`
`
`
`
`
`
`
`
`with many other people over the past years. They have commented on various parts
`
`
`
`
`
`
`
`
`
`
`
`
`
`of the book and include Chuan-Heng Ang, Walid Aref, James Arvo, Harvey H. Atkin-
`
`
`
`
`
`
`
`
`
`
`
`son, Thor Bestul, Sharat Chandran, Chiun-Hong Chien, Jiang-Hsing Chu, Leila De
`
`
`
`
`
`
`
`
`Floriani, Roger Eastman, Herbert Edelsbrunner, Claudio Esperanca, Christos Falout—
`
`
`
`
`
`
`
`
`
`
`
`sos, George (Gyuri) Fekete, Kikuo Fujimura, John Gannon, John Goldak, Erik Hoel,
`
`
`
`
`
`
`
`
`
`
`
`
`Liuqing Huang, Frederik W. Jansen, Ajay Kela, David Kirk, Per Ake Larson, Dani
`
`
`
`
`
`
`
`
`
`
`Lischinski, Don Meagher, David Mount, Randal C. Nelson, Glenn Pearson, Ron
`
`
`
`
`
`
`
`
`
`
`Sacks-Davis, Timos Sellis, Clifford A. Shaffer, Deepak Sherlekar, Li Tong, Brian
`
`
`
`
`
`
`
`
`
`
`
`
`Von Herzen, Peter Widmayer, and David Wise.
`I deeply appreciate their help.
`
`
`
`
`
`
`
`
`
`
`
`
`
`A GUIDE TO THE INSTRUCTOR
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`This book can be used in a second data structures course, one with emphasis on
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the representation of spatial data. The focus is on the use of the principle of divide-
`
`
`
`
`
`
`
`
`
`
`and-conquer for which hierarchical data structures provide a good demonstration.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Throughout the book both worst-case optimal methods and methods that work well in
`
`
`
`
`
`
`
`
`
`
`
`
`practice are emphasized in conformance with my view that the well-rounded computer
`
`
`
`
`
`
`
`
`
`
`
`
`
`scientist should be conversant with both types of algorithms. This material is more
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`than can be covered in one semester; but the instructor can reduce it as necessary. For
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`example, the detailed examples can be skipped or used as a basis of a term project or
`
`
`programming assignments.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The book can also be used to organize a course to be prerequisite to courses in
`
`
`
`
`
`
`
`
`computer graphics and solid modeling, computational geometry, database manage-
`
`
`
`
`
`
`
`
`
`
`ment systems, multidimensional searching, image processing, and VLSI design. The
`
`
`
`
`
`
`
`
`
`
`
`discussions of the representations of two-dimensional regions in Chapter 1, polygonal
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`representations in Chapter 4, and most of Chapter 5 are relevant to computer graphics
`
`
`
`
`
`
`
`
`
`
`
`and solid modeling. The discussions of plane-sweep methods and their associated
`
`
`
`
`
`
`
`
`
`
`
`
`
`data structures such as segment trees, interval trees, and priority search trees in Sec—
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(ions 3.2 and 3.3 and point
`location and associated data structures such as the
`
`Page 11 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 11 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`

`

`CONTENTS
`
`
`
`Preface
`
`
`
`
`vii
`
`
`INTRODUCTION
`
`
`
`Basic Definitions
`
`
`
`
`
`
`1.2 Overview of Quadtrees and Octrees
`
`
`
`
`
`
`
`
`1.3 History of the Use of Quadtrees and Octrees
`
`
`
`
`1.4
`Space Decomposition Methods
`
`
`
`Polygonal Tilings
`1.4.1
`
`
`1.4.2 Nonpolygonal Tilings
`
`
`Space Requirements
`
`1.1
`
`1.5
`
`
`
`
`
`1
`
`
`
`2
`
`
`
`
`
`10
`
`
`
`
`
`
`
`17
`
`26
`
`32
`
`16
`
`
`43
`
`44
`
`46
`
`48
`
`49
`
`54
`
`64
`
`66
`
`68
`
`73
`
`77
`
`8O
`
`80
`
`85
`
`86
`
`92
`
`
`
`
`
`
`
`POINT DATA
`
`
`Introduction
`2.1
`
`
`
`2.2 Nonhierarchical Data S