Apparatus storing a presentation of topological structures and methods of building and searching the representation

Claim 1

Apparatus storing a representation of a topological structure having topological features, comprising: a) a data storage medium; and b) a digital data base stored on said data storage medium, said digital data base including a plurality of carrier blocks of data representing the topological features at a given level of detail, said data of each one of said carrier blocks being a representation of a carrier which is a closed set including in its interior a given topological object, and wherein said closed set is a smallest closed set and is a sub-complex X i of a topological complex X, the sub-complex X i having a set of n-cells, where 0≦n≦ the dimension of the topological structure and the totality of said plurality of carrier blocks covers the topological complex X.

Claim 10

A method of building a digital data base representing a given topological structure, using a programmed computer, the digital data base having first and second levels of carrier blocks of data that are topologically equivalent, each of said carrier blocks of said first level having a topological sub-complex X i corresponding to an element A i of a partition P at the first level, each said sub-complex X i having n-cells, where n=0, 1, 2 . . . , and the 2-cells c 2 i of the sub-complex X i being mutually adjacent, and where the totality of the carrier blocks of data of the first level constitute a topological complex X, and the totality of the carrier blocks of data of the second level constitute a topological complex X', comprising the steps of: a) providing each said sub-complex X i on a data storage medium; b) for each said sub-complex X i , fusing all the 2-cells c 2 i in one said sub-complex X i to form a single 2-cell c' 2 i ; c) identifying a 1-complex of 1-cells c 1 i on the boundary of the single 2-cells c' 2 i and the 0-cells c 0 i bounding those 1-cells c 1 i , where those 0-cells c 0 i incident to t 1-cells c 1 i are essential 0-cells c 0 i , where t=2; d) constructing connected chains of 1-cells c 1 i so that each chain c 1 i is bounded by the essential 0-cells c 0 i , where these chains of 1-cells c 1 i are common to adjacent sub-complexes X i or on the boundary of the entire complex X; e) fusing each chain of 1-cells c 1 i to form a 1-cell c' 1 i ; and f) for each essential 0-cell c 0 i , creating a chain of 0-cells c 0 k having a single 0-cell and mapping this chain into the 0-cell c' 0 m as a copy of the essential 0-cell c 0 i , whereby the n-cells c' 2 i , c' 1 i and c' 0 m constitute the topological complex X'.

Claim 11

A method of building a digital data base representing a given topological structure, using a programmed computer, the digital data base having first and second levels of carrier blocks of data that are topologically equivalent, each of said carrier blocks of said first level having a topological sub-complex X i corresponding to an element A i of a partition P at the first level, each said sub-complex X i having n-cells, where n=0, 1, 2 . . . , and the 2-cells c 2 i of the sub-complex X i being mutually adjacent, and where the totality of the carrier blocks of data of the first level constitute a topological complex X, and the totality of the carrier blocks of data of the second level constitute a topological complex X', comprising the steps of: a) providing each said sub-complex X i on a data storage medium; b) for each said sub-complex X i , fusing all the 2-cells c 2 i in one said sub-complex X i to form a single 2-cell c' 2 i ; c) identifying a 1-complex of 1-cells c 1 i on the boundary of the single 2-cells c' 2 i and the 0-cells c 0 i bounding those 1-cells c 1 i , where those 0-cells c 0 i incident to t 1-cells c 1 i are essential 0-cells c 0 i , where t=2; d) constructing connected chains of 1-cells c 1 i so that each chain c 1 i is bounded by the essential 0-cells c 0 i , where these chains of 1-cells c 1 i are common to adjacent sub-complexes X i or on the boundary of the entire complex X; e) fusing each chain of 1-cells c 1 i to form a 1-cell c' 1 i ; and f) for each essential 0-cell c 0 i , creating a chain of 0-cells c 0 k having a single 0-cell and mapping this chain into the 0-cell c' 0 m as a copy of the essential 0-cell c 0 i , whereby the n-cells c' 2 i , c' 1 i and c' 0 m constitute the topological complex X'.

Claim 16

A method of building a digital data base, representing a given topological structure, using a programmed computer, the digital data base corresponding to a complex X having a plurality of elements A i ={c 2 j } of a partition P and a plurality of n-cells corresponding to topological features of the topological structure, wherein n=0, 1, 2, comprising the steps of: a) initializing a counter k; b) selecting an arbitrary 2-cell c 2 j in the complex X not already included in a prior element A i in the partition P; c) incrementing the counter k and initializing a register A k storing element A k to store only the selected 2-cell c 2 j of a sub-complex X k ; d) adding all 1-cells and 0-cells incident to the selected 2-cells c 2 j to provide a sub-complex X k being a topological closed set; e) selecting another 2-cell c 2 j in the complex X not already included in a prior element A i and adjacent a 2-cell c 2 j in the sub-complex X k ; f) testing whether adding the 2-cell c 2 j selected in step e) and all 1-cells and 0-cells incident thereto to the sub-complex X k would cause the sub-complex X k to exceed a given threshold of complexity; g) going to step h) or step i) if the test of step f) does not or does show, respectively, the given threshold being exceeded or not being exceeded; h) adding the 2-cell c 2 j tested in step f) to register A k and adjoining this 2-cell c 2 j and all its incident 1-cells and 0-cells to keep the sub-complex X k a closed set; i) returning to step e); j) since element A k and sub-complex X k are complete, adding element A k to a register P storing the partition P and storing the sub-complex X k ; and k) going to step b) if there remains any 2-cell c 2 j in some element A i .

Claim 17

A method of building a digital data base, representing a given topological structure, using a programmed computer, the digital data base corresponding to a complex X having a plurality of elements A i ={c 2 j } of a partition P and a plurality of n-cells corresponding to topological features of the topological structure, wherein n=0, 1, 2, comprising the steps of: a) initializing a counter k; b) selecting an arbitrary 2-cell c 2 j in the complex X not already included in a prior element A i in the partition P; c) incrementing the counter k and initializing a register A k storing element A k to store only the selected 2-cell c 2 j of a sub-complex X k ; d) adding all 1-cells and 0-cells incident to the selected 2-cells c 2 j to provide a sub-complex X k being a topological closed set; e) selecting another 2-cell c 2 j in the complex X not already included in a prior element A i and adjacent a 2-cell c 2 j in the sub-complex X k ; f) testing whether adding the 2-cell c 2 j selected in step e) and all 1-cells and 0-cells incident thereto to the sub-complex X k would cause the sub-complex X k to exceed a given threshold of complexity; g) going to step h) or step i) if the test of step f) does not or does show, respectively, the given threshold being exceeded or not being exceeded; h) adding the 2-cell c 2 j tested in step f) to register A k and adjoining this 2-cell c 2 j and all its incident 1-cells and 0-cells to keep the sub-complex X k a closed set; i) returning to step e); j) since element A k and sub-complex X k are complete, adding element A k to a register P storing the partition P and storing the sub-complex X k ; and k) going to step b) if there remains any 2-cell c 2 j in some element A i .

Claim 18

A method of searching a digital data base using a programmed computer, the digital data base having a hierarchy of levels of carrier blocks of data, each level in the hierarchy, constituting topological complexes X, X', X" . . . , each of the complexes X, X', X" . . . containing successively more generalized information and the complex containing the most generalized information being the root, each of the complexes X, X', X" . . . constituting n-cells, where n=0, 1,2 . . . and the digital data base representing a topological structure, comprising the steps of: a) initializing a first list of selected cells and a second list of current carrier blocks; b) setting the second list to be the root; c) setting the current hierarchical level to be the root; d) selecting from the second list of current carrier blocks, the 0-cells, 1-cells and 2-cells that fall within a specified range from a point; e) exiting if the current hierarchical level is 0; f) replacing the second list of current carrier blocks with another list containing one carrier block for each 2-cell at the current level in the first list of selected cells, whereby each said one carrier block of said other list is at the next level of the hierarchy; g) decrementing the current level; and h) returning to step d).

Claim 19

A method of searching a digital data base using a programmed computer, the digital data base having a hierarchy of levels of carrier blocks of data, each level in the hierarchy, constituting topological complexes X, X', X" . . . , each of the complexes X, X', X" . . . containing successively more generalized information and the complex containing the most generalized information being the root, each of the complexes X, X', X" . . . constituting n-cells, where n=0, 1,2 . . . and the digital data base representing a topological structure, comprising the steps of: a) initializing a first list of selected cells and a second list of current carrier blocks; b) setting the second list to be the root; c) setting the current hierarchical level to be the root; d) selecting from the second list of current carrier blocks, the 0-cells, 1-cells and 2-cells that fall within a specified range from a point; e) exiting if the current hierarchical level is 0; f) replacing the second list of current carrier blocks with another list containing one carrier block for each 2-cell at the current level in the first list of selected cells, whereby each said one carrier block of said other list is at the next level of the hierarchy; g) decrementing the current level; and h) returning to step d).

Claim 20

A method of searching a digital data base using a programmed computer, the digital date base having a plurality of carrier blocks at a given level constituting a topological complex, each of the carrier blocks containing topological n-cells, comprising the steps of: a) initializing a first list of selected n-cells and a second list of current carrier blocks; b) setting the second list of current carrier blocks to be a given carrier block; c) selecting from the second list of current carrier blocks the n-cells that fall within a given range of a point; d) exiting if no n-cells selected in step c) is on a boundary of a carrier corresponding to the carrier block to output the first list of selected n-cells; e) for each n-cell in the first list, if the selected n-cell of step c) is on the boundary of a carrier and another carrier block corresponding to an adjacent carrier is not in the second list, adding that other carrier block to the second list; and f) returning to step c).

Claim 21

A method of searching a digital data base using a programmed computer, the digital date base having a plurality of carrier blocks at a given level constituting a topological complex, each of the carrier blocks containing topological n-cells, comprising the steps of: a) initializing a first list of selected n-cells and a second list of current carrier blocks; b) setting the second list of current carrier blocks to be a given carrier block; c) selecting from the second list of current carrier blocks the n-cells that fall within a given range of a point; d) exiting if no n-cells selected in step c) is on a boundary of a carrier corresponding to the carrier block to output the first list of selected n-cells; e) for each n-cell in the first list, if the selected n-cell of step c) is on the boundary of a carrier and another carrier block corresponding to an adjacent carrier is not in the second list, adding that other carrier block to the second list; and f) returning to step c).

Claim 22

A method of searching a digital data base using a programmed computer, the digital data base having a hierarchy of carrier blocks and each level in the hierarchy of carrier blocks of data constituting topological complexes X, X', X" . . . , each of the complexes containing successively more generalized information and the complex containing the most generalized information being the root, each of the complexes constituting topological n-cells, the method being searching from a lesser detailed hierarchical level to the root, comprising the steps of: a) initializing a first list of selected cells and a second list of current carrier blocks; b) setting the second list of current carrier blocks to a given carrier block; c) selecting from the second list of current carrier blocks the n-cells that fall within a specified range of a point; d) exiting if the current level is the root to output the first list of selected cells; and e) replacing the current carrier blocks in the second list with a single carrier block at the next more generalized level in the hierarchy.

Claim 23

A method of searching a digital data base using a programmed computer, the digital data base having a hierarchy of carrier blocks and each level in the hierarchy of carrier blocks of data constituting topological complexes X, X', X" . . . , each of the complexes containing successively more generalized information and the complex containing the most generalized information being the root, each of the complexes constituting topological n-cells, the method being searching from a lesser detailed hierarchical level to the root, comprising the steps of: a) initializing a first list of selected cells and a second list of current carrier blocks; b) setting the second list of current carrier blocks to a given carrier block; c) selecting from the second list of current carrier blocks the n-cells that fall within a specified range of a point; d) exiting if the current level is the root to output the first list of selected cells; and e) replacing the current carrier blocks in the second list with a single carrier block at the next more generalized level in the hierarchy.