Nt1310 Unit 3 Programming Assignment

Fall 1999

CMSC 420 Hanan Samet

Programming Assignment 1: A Data Structure For VLSI Applications1

Abstract In this assignment you are required to implement an information management system for handling data similar to that used in VLSI applications. In such an environment the primary entities are small rectangles and the problem in which we are interested is how to manage a large collection of them. In the following we trace the development of a variant of the quadtree data structure that can be used for such a problem. Your task is to implement this data structure in such a way that a number of operations can be efficiently handled. An example JAVA applet for the data structure can be found on the home page of the class. This assignment…show more content…
For the third part, you are to write a PASCAL (or C or C++) program to implement the data structure and operations (1)-(8). For the fourth part, you are to implement operations (9)-(13). Operations (14)-(16) are optional and you will get extra credit if you turn them in with part four.

c 1999 by Hanan Samet. No part of this document may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the express prior permission of the author.

1 Copyright

1 Region-Based Quadtrees
The quadtree is a member of a class of hierarchical data structures that are based on the principle of recursive decomposition. As an example, consider the point quadtree of Finkel and Bentley [1] which should be familiar to you as it is simply a multidimensional generalization of a binary search tree. In two dimensions each node has four subtrees corresponding to the directions NW, NE, SW, and SE. Each subtree is commonly referred to as a quadrant or subquadrant. For example,…show more content…
3.1 Insertion Rectangles are inserted into a RECT quadtree by searching for the position which they are to occupy. We assume that the rectangle does not intersect (i.e., overlap) an existing rectangle. In particular, a rectangle is inserted into a RECT quadtree by traversing the tree in preorder and successively clipping it against the blocks corresponding to the nodes. Clipping is important because it enables us to avoid looking at areas where the rectangle cannot be inserted. If the rectangle can be inserted into the node (i.e., the node is empty), say P, then we are done. Otherwise, a list, say L, is formed containing the rectangle and any r-pieces already present in the node, P is split, and the insertion process is recursively invoked to attempt to insert the elements of L in the four sons of P. For example, Figure 4a–e shows how the RECT quadtree for the collection of rectangles in Figure 1 is constructed in incremental fashion for rectangles A, B, C, D, and E. We assume that the empty collection is represented by a one node tree having no