US5872718A — Advanced modular cell placement system

Claim 1

Independent Claim 123 words

A method for locating a plurality of elements on a surface associated by a list, comprising the steps of: a. forming a neighborhood defined as a set of elements located a relatively short spatial distance from a target element; b. ordering elements within each neighborhood according to their relative spatial distance from said target element; c. preplacing said elements within a two-dimensional abstraction of said surface; d. iteratively subdividing said surface into a plurality of regions; e. assigning elements to said plurality of regions; f. moving said elements based on affinities for relocating said elements; g. levelizing element density over the surface based on relationships between various elements; h. relocating any overlapping elements; and g. performing a final cell adjustment for element positions.

Claim 2

Independent Claim 123 words

A method for locating a plurality of elements on a surface associated by a list, comprising the steps of: a. forming a neighborhood defined as a set of elements located a relatively short spatial distance from a target element; b. ordering elements within each neighborhood according to their relative spatial distance from said target element; c. preplacing said elements within a two-dimensional abstraction of said surface; d. iteratively subdividing said surface into a plurality of regions; e. assigning elements to said plurality of regions; f. moving said elements based on affinities for relocating said elements; g. levelizing element density over the surface based on relationships between various elements; h. relocating any overlapping elements; and g. performing a final cell adjustment for element positions.

Claim 3

Dependent Claim 104 words

The method of claim 1, wherein said preplacing step comprises: a. establishing an initial location for all elements; b. iteratively performing a one dimensional preplacement optimization technique; c. subdividing the surface into subregions by dividing the surface in one direction; d. performing a levelizing cut point procedure; e. performing a median control procedure; f. iterating said levelizing cut point procedure and median control procedure a first predetermined number of times; g. computing a cost function; and h. repeating said iterating said levelizing cut point procedure and median control procedure step and said computing a cost function step until a predetermined ending criterion is achieved.

Claim 4

Dependent Claim 56 words

The method of claim 2, wherein said iterative performance of a one dimensional preplacement optimization technique step comprises: a. computing coordinates for related elements; b. determining a weight associated with each element; and c. calculating a new cell coordinate for each cell based on the coordinates from said computing step and weights from said determining step.

Claim 5

Dependent Claim 42 words

The method of claim 2, wherein said element moving step comprises computing a combination of affinities from among the group of affinities including affinities for elements clustered together, affinities based on region capacity, and affinities based on groups crossing divisions between regions.

Claim 6

Dependent Claim 42 words

The method of claim 1, wherein said element moving step comprises computing a combination of affinities from among the group of affinities including affinities for elements clustered together, affinities based on region capacity, and affinities based on groups crossing divisions between regions.

Claim 7

Dependent Claim 25 words

The system of claim 1 wherein said element ordering step comprises assigning coordinates to each element, iterating element coordinates, and assigning the elements to neighborhoods.

Claim 8

Independent Claim 131 words

A system for optimally locating a plurality of elements on a surface, comprising the steps of: a. constructing a plurality of neighborhoods containing elements positionally related to one another; b. initially evaluating the lowest level of region hierarchy; c. iteratively developing a logical one-dimensional preplacement of elements on said surface; d. performing an affinity driven discrete preplacement optimization; e. evaluating whether a highest level of regional hierarchy has been attained; f. iteratively performing a dispersion driven spring system to levelize cell density and an unconstrained sinusoidal optimization; g. executing a density levelizing procedure; h. iteratively optimizing while controlling element densities; i. removing element overlap; j. iteratively optimizing for desired spacing between elements, adjusting element spacing, and permuting elements; k. locating elements on grid lines; and l. iteratively performing functional sieve crystallization.

Claim 9

Independent Claim 131 words

A system for optimally locating a plurality of elements on a surface, comprising the steps of: a. constructing a plurality of neighborhoods containing elements positionally related to one another; b. initially evaluating the lowest level of region hierarchy; c. iteratively developing a logical one-dimensional preplacement of elements on said surface; d. performing an affinity driven discrete preplacement optimization; e. evaluating whether a highest level of regional hierarchy has been attained; f. iteratively performing a dispersion driven spring system to levelize cell density and an unconstrained sinusoidal optimization; g. executing a density levelizing procedure; h. iteratively optimizing while controlling element densities; i. removing element overlap; j. iteratively optimizing for desired spacing between elements, adjusting element spacing, and permuting elements; k. locating elements on grid lines; and l. iteratively performing functional sieve crystallization.

Claim 10

Independent Claim 80 words

A system for optimally locating a plurality of elements on a surface, comprising: a. forming a neighborhood defined as a set of elements located a relatively short spatial distance from a target element; b. ordering elements within each neighborhood according to their relative spatial distance from said target element; c. optimizing placement by performing a regional hierarchical descent; d. levelizing element densities over said surface; and e. further optimizing element locations by adjusting element position based on relationships between elements.

Claim 11

Independent Claim 80 words

A system for optimally locating a plurality of elements on a surface, comprising: a. forming a neighborhood defined as a set of elements located a relatively short spatial distance from a target element; b. ordering elements within each neighborhood according to their relative spatial distance from said target element; c. optimizing placement by performing a regional hierarchical descent; d. levelizing element densities over said surface; and e. further optimizing element locations by adjusting element position based on relationships between elements.

Claim 12

Independent Claim 140 words

An apparatus for locating a plurality of elements on a surface associated by a list, said apparatus comprising: a. means for forming a neighborhood defined as a set of elements located a relatively spatial short distance from a target element; b. means for ordering elements within each neighborhood according to their relative spatial distance from said target element; c. means for preplacing said elements within a two-dimensional abstraction of said surface; d. means for iteratively subdividing said surface into a plurality of regions; e. means for assigning elements to said plurality of regions; f. means for moving said elements based on affinities for relocating said elements; g. means for levelizing element density over the surface based on relationships between various elements; h. means for relocating any overlapping elements; and g. means for performing a final cell adjustment for element positions.

Claim 13

Independent Claim 140 words

An apparatus for locating a plurality of elements on a surface associated by a list, said apparatus comprising: a. means for forming a neighborhood defined as a set of elements located a relatively spatial short distance from a target element; b. means for ordering elements within each neighborhood according to their relative spatial distance from said target element; c. means for preplacing said elements within a two-dimensional abstraction of said surface; d. means for iteratively subdividing said surface into a plurality of regions; e. means for assigning elements to said plurality of regions; f. means for moving said elements based on affinities for relocating said elements; g. means for levelizing element density over the surface based on relationships between various elements; h. means for relocating any overlapping elements; and g. means for performing a final cell adjustment for element positions.

Claim 14

Dependent Claim 121 words

The apparatus of claim 9, wherein said means for replacing comprises: a. means for establishing an initial location for all elements; b. means for iteratively performing a one dimensional preplacement optimization technique; c. means for subdividing the surface into subregions by dividing the surface in one direction; d. means for performing a levelizing cut point procedure; e. means for performing a median control procedure; f. means for iterating said levelizing cut point procedure and median control procedure a first predetermined number of times; g. means for computing a cost function; and h. means for repeating operation of said means for iterating said levelizing cut point procedure and said means for computing a cost function until a predetermined ending criterion is achieved.

Claim 15

Dependent Claim 71 words

The apparatus of claim 10, wherein said means for iteratively performing a one dimensional preplacement optimization technique comprises: a. means for computing coordinates for related elements; b. means for determining a weight associated with each element; and c. means for calculating a new cell coordinate for each cell based on the coordinates from the operation of said means for computing coordinates and from the operation of said means for determining weights.

Claim 16

Dependent Claim 45 words

The apparatus of claim 10, wherein said means for moving elements comprises means for computing a combination of affinities from among the group of affinities including affinities for elements clustered together, affinities based on region capacity, and affinities based on groups crossing divisions between regions.

Claim 17

Dependent Claim 45 words

The apparatus of claim 9, wherein said means for moving elements comprises means for computing a combination of affinities from among the group of affinities including affinities for elements clustered together, affinities based on region capacity, and affinities based on groups crossing divisions between regions.

Claim 18

Dependent Claim 28 words

The apparatus of claim 9 wherein said means for ordering elements comprises means for assigning coordinates to each element, iterating element coordinates, and assigning the elements to neighborhoods.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2002-02-15	2002-08-17	2003-02-16	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2006-02-15	2006-08-17	2007-02-16	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2010-02-15	2010-08-17	2011-02-16	$7700.00	Window Closed / Lapsed

Advanced modular cell placement system

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag