`
`The Design and
`
`
`Analysis of
`
`
`Spatial Data
`
`Structures
`
`
`
`
`Page | 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 * Wokingham, England * Amsterdam
`
`
`
`
`
`
`Bonn * Sydney * Singapore * Tokyo * Madrid * 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
`
`
`
`
`
`
`
`
`
`Manyof 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 beenprinted in initial caps orall 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.D35S26
`005.7’3 —dc19
`
`
`
`2. Computer graphics.
`
`
`
`
`
`
`
`1989
`
`
`
`
`
`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.
`
`
`
`4567891011 1213 14-MA-97 96 95 94
`
`
`
`
`
`
`
`
`
`
`Credits:
`
`Thor Bestul created the coverart.
`
`
`
`
`
`
`Gyuri Fekete generated Figure 1.16; Daniel DeMenthon, Figures 1.20, 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 I. Fundamentals, JEEE 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 respectto 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-710. 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 permission 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 myparents, 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 commonfor 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 polygonsthat are isolated (e.g., lakes), adjacent (e.g., nations), or nested (e.g.,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`contours). Clearly the variations are large.
`
`
`
`
`
`
`Manyofthe 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`In
`dimensions). As we shall see, the term quadtree has taken on a generic meaning.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`this book, it is my goal to show how a numberof hierarchical data structures used in
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`different domainsare related to each other and to quadtrees. My presentation concen-
`
`
`
`
`
`
`
`
`
`
`
`
`trates on these different representations and illustrates how a numberof 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 performingset
`
`
`
`
`
`
`
`
`
`
`
`
`operations. Manyof the operations described can often be performed asefficiently, 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
`
`
`I
`
`
`PREFACE
`
`
`
`
`
`
`
`
`
`As an example of the type of problems to which the techniques describedin this
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`book are applicable, consider a cartographic database consisting of a number of maps
`
`
`
`
`
`
`
`
`
`
`and sometypical 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 mapsare represented. For
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`example, since areas where com 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 corn-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 roadsintersect 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 whetherin fact the rectangles do overlap. If they do not, the search is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`terminated. If an intersection is possible, more work mayhave to be done, depending
`
`
`
`
`
`
`
`
`
`
`
`
`
`on which methodof 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 andits
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`adjacentstates 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 numberof different data structures. The aim is to gain the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ability to evaluate them and to determine their applicability. Two problemsare 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 (Chapter4).
`
`
`
`
`
`
`
`
`
`
`
`
`
`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
`
`
`ll
`
`
`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 designedto 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].
`
`
`
`
`
`
`Chapter4 treats the hierarchical representation of curvilinear data. The primary
`
`
`
`
`
`
`
`
`
`focus is on the representation of polygonal maps. The goalis to be able to solve. the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`point location problem. Quadtree-like solutions are compared with those from com-
`
`
`
`
`
`
`
`
`
`
`putational geometry suchas the K-structure [Kirk83] and the layered dag [Edel86a].
`
`
`
`
`
`
`
`
`
`
`
`
`In this
`Chapter 5 looks at the representation of three-dimensional region data.
`
`
`
`
`
`
`
`
`
`
`
`case, a numberof 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 numberof topics for which justice requires a considerably more
`
`
`
`
`
`
`
`
`
`
`
`
`detailed treatment. However, due to space limitations, I have omitted a detailed dis-
`
`
`
`
`
`
`
`
`
`
`
`cussion of them andinstead 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 someof 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 also a numberof 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 Mehlhorn’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
`
`Il
`
`
`
`
`xill
`
`
`
`
`
`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 |, 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 importantin the field of VLSI design.
`
`
`
`
`
`
`
`
`
`The natural homefor 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 (GIS). 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
`
`
`
`Ml
`
`
`PREFACE
`
`
`
`
`
`
`
`Shamos [Prep85] and Edelsbrunner [Edel87] (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 [Edel83c, Edel88], 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`somestructures 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.
`
`
`
`
`
`
`
`
`
`
`
`
`Myapproachis an algorithmic one. Wheneverpossible, I have tried to motivate
`
`
`
`
`
`
`
`
`
`
`
`
`is of
`it
`critical steps in the algorithms by a liberal use of examples.
`I feel
`that
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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-codeso that readers can see how the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ideas can be applied. The pseudo-codeis 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 [Kern78],
`
`
`
`
`
`
`
`
`
`
`
`
`PASCAL [Jens74], SAIL [Reis76], and ALGOL W [Baue68].
`Its basic features are
`
`
`
`
`
`
`
`
`
`
`
`
`described in the Appendix. However, the actual codeis not crucial to understanding
`
`
`
`
`
`
`
`
`
`
`
`
`
`the techniques, and it maybe skipped on a first reading. The index indicates the page
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`numbers where the code for each algorithm is found.
`
`
`
`
`
`
`
`
`
`In manycases I also give an analysis of the space and time requirements ofdif-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ferent data structures and algorithms. The analysis is usually of an asymptotic nature
`
`
`
`
`
`
`
`
`
`
`
`
`
`and is in terms of big O and Q notation [Knut76]. The big O notation denotes an
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`upper bound. For example, if an algorithm takes O(log,N) time, then its worst-case
`
`
`
`
`
`
`
`
`
`
`
`
`
`behavior is never any worse than log,N. The Q notation denotes a lower bound. As
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`an example of its use, consider the problem of sorting N numbers. When wesaythat
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`sorting is Q(N:log>N) we meanthat given any algorithm for sorting, there is some set
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`of N 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 numberoffields in a record,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`are often given. These numbers are meant only to amplify the discussion. They are
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`notto be taken literally, as improvements are always possible once a specific applica-
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion is analyzed morecarefully.
`
`
`
`
`
`Each chapter contains a substantial number of exercises. Many ofthe exercises
`
`
`
`
`
`
`
`
`
`
`
`develop further the material in the text as a meansof testing the reader’s understand-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ing, as well as suggesting future directions. When the exercise orits solution is not
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`my own, I have preceded it with the nameof 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
`
`
`Il
`
`
`xi
`
`
`contain the solution, are provided for a substantial numberof the exercises that do nat
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`require programming. Readers are cautionedto try to solve the exercises before turn-
`
`
`
`
`
`
`
`
`
`
`
`
`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 myfirst 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]. Notall of the references that appearin 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 ofliterature 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 whichit 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 workis cited or a credit is made.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ACKNOWLEDGMENTS
`
`
`
`
`
`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 muchoftheir time and have gone overcritical
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 beena true inspiration to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`I deeply cherish our association.
`me.
`
`
`
`
`
`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 muchinteraction 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 Tamminen taught mé
`
`
`
`
`
`
`
`
`
`
`
`
`solid modeling and representations for multiattribute data, and Michael B. Dillencourt
`
`
`
`
`
`
`
`
`
`
`
`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 '"
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`thank Richard Antony, Y. T. Chien, Su-shing Chen, Hank Cook, Phil Emmerman, Jc«
`
`
`
`
`
`
`
`
`
`
`
`
`
`Rastatter, Alan Saalfeld, and Larry Tokarcik.
`I am appreciative of their support.
`
`
`
`
`
`
`
`
`
`
`
`
`Many people helped mein the process of preparing the book for publicatior
`
`
`
`
`
`
`
`
`
`
`
`
`
`Acknowledgments are due to Rene McDonald for coordinating the day-to-day matters
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 10 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`Page 10 of 448
`
`Unified Patents Exhibit 1005 App'x A-N
`
`
`
`xii
`
`
`I
`
`
`PREFACE
`
`
`
`
`
`
`
`
`
`
`
`of getting the book out and copyediting; to Scott Carson, Emery Jou, and Jim Purtilo
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`for TROFF aSsistance beyondthe call of duty; to Marisa Antoy and Sergio Antoy for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`designing and implementing the algorithm formatter used to typeset the algorithms; to
`
`
`
`
`
`
`
`
`
`
`
`
`Barbara Burnett, Michael B. Dillencourt, and Sandra Germanfor help with the index;
`
`
`
`
`
`
`
`
`
`
`
`
`
`to Jay Weberfor setting up the TROFF macrofiles so that I can keep track of symbolic
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`namesandthus 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 Companyfor their encouragement and confidencein 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.
`
`
`
`
`
`
`
`
`
`
`Throughoutthe book both worst-case optimal methods and methodsthat 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 segmenttrees, interval trees, and priority search trees in Sec-
`
`
`
`
`
`
`
`
`
`
`
`
`
`dons 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
`
`
`1.1
`
`
`1.2
`
`
`1.4
`
`
`1.3
`
`INTRODUCTION
`
`Basic Definitions
`
`
`Overview of Quadtrees and Octrees
`
`
`
`
`
`History of the Use of Quadtrees and Octrees
`
`
`
`
`
`
`
`Space Decomposition Methods
`
`
`
`Polygonal Tilings
`1.4.1.
`
`
`
`1.4.2. Nonpolygonal Tilings
`
`
`Space Requirements
`
`
`1.5
`
`
`
`
`
`
`
`
`
`10
`
`16
`
`
`
`
`
`
`
`26
`
`32
`
`
`17
`
`1
`
`
`
`2
`
`
`
`POINT DATA
`
`
`Introduction
`2.1
`
`
`Nonhierarchical Data Structures
`2.2
`
`
`
`2.3
`Point Quadtrees
`
`
`
`Insertion
`2.3.1
`
`2.3.2 Deletion
`
`2.3.3.
`Search
`
`k-d Trees
`
`
`2.4.1
`Insertion
`
`2.4.2 Deletion
`
`2.4.3
`Search
`
`
`2.4.4