Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-01-31
2004-03-02
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06701306
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed toward the field of computers and electronic design automation, and more particularly towards storing representations of polygons for computer and electronic design automation applications.
2. Art Background
Many applications today analyze multidimensional data records. A multidimensional data record contains a number of data values, which are defined along a number of dimensions (also called attributes or keys) in a multidimensional space. Such records are typically stored in data files or databases.
A spatial data record is one type of multidimensional data record. Spatial data records typically describe the attributes (e.g., the position, size, shape, etc.) of geometric objects, such as points, lines, polygons, regions, surfaces, volumes, etc. Spatial records are used in many fields, including computer-aided design, computer graphics, data management systems, robotics, image processing, geographic information systems, pattern recognition, and computational geometry.
Effective data structures are needed to organize multidimensional and spatial data records efficiently, in order to optimize the time for querying these records. For instance, a sequential list of the multidimensional data records provides the simplest way of storing the records. However, the time needed for performing a query on such a list is intolerably high in most cases since each record in the list needs to be examined for each query. Numerous multidimensional data structures have been proposed for organizing multidimensional and spatial data records. Hanan Samet,
The Design and Analysis of Spatial Data Structures
, Addison-Wesley Publishing, 1990, includes a review of many of these data structures.
Multidimensional data structures include hierarchical data structures. Hierarchical structures are based on the principle of recursive decomposition of the data space (i.e., the object space or the image space). In other words, these data structures are created by recursively dividing the data space, and storing the data records according to their location in the divided space. Quadtrees and k-d trees are two types of hierarchical data structures.
Electronic design automation (“EDA”) applications assist engineers in designing integrated circuits (“IC's”). Specifically, these applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts. These layouts are formed by geometric shapes that represent layers of different materials and devices on IC's. Spatial data records define the spatial attributes of many of these geometric shapes. For instance, spatial data records are used to define geometric shapes that represent conductive interconnect lines. Interconnect lines route signals on the IC's. These lines are sometimes referred to as wire segments or segs. EDA applications typically characterize interconnect lines as rectangles. The rectangles depict interconnect lines deposed on the IC in a vertical and/or horizontal directions, relative to the boundaries of the integrated circuit. As described fully below, the present invention characterizes interconnect lines as polygons. The polygons depict interconnect lines deposed on the IC in diagonal directions, relative to the boundaries of the integrated circuit. Thus, it is desireable to create mechanisms to manipulate and store polygons in a multi-dimensional space.
SUMMARY OF THE INVENTION
Geometric objects, such as polygons, are defined in a multi-dimensional data space. The geometric objects are represented by data segments for processing in a computer. “N” dimensional hierarchical trees, or “ng” trees, are generated to organize the data segments into “outside child nodes” and “inside child nodes” in accordance with a discriminator value. The discriminator value is selected for each layer or discriminator dimension in the ng tree. For the ng tree, one of “n” sides of a polygon is selected as the discriminator value. To create the ng tree, data segments are designated as “outside child nodes” if a data segment is outside the plane defined by the discriminator value, and data segments are selected as “inside child nodes” if the data segment is inside the plane defined by the discriminator value. This process of partitioning data segments into inside child nodes and outside child nodes is repeated recursively through each level of the ng tree.
REFERENCES:
patent: 5598559 (1997-01-01), Chaudhuri
patent: 5659725 (1997-08-01), Levy et al.
patent: 5781906 (1998-07-01), Aggarwal et al.
patent: 5845270 (1998-12-01), Schatz et al.
patent: 5857180 (1999-01-01), Hallmark et al.
patent: 6085147 (2000-07-01), Myers
patent: 6263339 (2001-07-01), Hirsch
patent: 6292810 (2001-09-01), Richards
patent: 6317750 (2001-11-01), Tortolani et al.
patent: 6567814 (2003-05-01), Bankier et al.
patent: 6591235 (2003-07-01), Chen et al.
Kronmiller Tom
Teig Steven
Cadence Design Systems Inc.
Mizrahi Diane D.
Stattler Johansen & Adeli LLP
LandOfFree
Methods and apparatus for manipulating polygons in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for manipulating polygons in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for manipulating polygons in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3282756