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

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.sub.i corresponding to an element A.sub.i of a partition P at the first level, each said sub-complex X.sub.i having n-cells, where n=0, 1, 2 . . . , and the 2-cells c.sup.2.sub.i of the sub-complex X.sub.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.sub.i on a data storage medium;
• b) for each said sub-complex X.sub.i, fusing all the 2-cells c.sup.2.sub.i in one said sub-complex X.sub.i to form a single 2-cell c'.sup.2.sub.i ;
• c) identifying a 1-complex of 1-cells c.sup.1.sub.i on the boundary of the single 2-cells c'.sub.2.sub.i and the 0-cells c.sup.0.sub.i bounding those 1-cells c.sup.1.sub.i, where those 0-cells c.sup.0.sub.i incident to t 1-cells c.sup.1.sub.i are essential 0-cells c.sup.0.sub.i, where t=2;
• d) constructing connected chains of 1-cells c.sup.1.sub.i so that each chain c.sup.1.sub.i is bounded by the essential 0-cells c.sup.0.sub.i, where these chains of 1-cells c.sup.1.sub.i are common to adjacent sub-complexes X.sub.i or on the boundary of the entire complex X;
• e) fusing each chain of 1-cells c.sup.1.sub.i to form a 1-cell c'.sup.1.sub.i ;
• and
• f) for each essential 0-cell c.sup.0.sub.i, creating a chain of 0-cells c.sup.0.sub.k having a single 0-cell and mapping this chain into the 0-cell c'.sup.0.sub.m as a copy of the essential 0-cell c.sup.0.sub.i, whereby the n-cells c'.sup.2.sub.i, c'.sup.1.sub.i and c'.sup.0.sub.m constitute the topological complex X'.

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.sub.i ={c.sup.2.sub.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.sup.2.sub.j in the complex X not already included in a prior element A.sub.i in the partition P;
• c) incrementing the counter k and initializing a register A.sub.k storing element A.sub.k to store only the selected 2-cell c.sup.2.sub.j of a sub-complex X.sub.k ;
• d) adding all 1-cells and 0-cells incident to the selected 2-cells c.sup.2.sub.j to provide a sub-complex X.sub.k being a topological closed set;
• e) selecting another 2-cell c.sup.2.sub.j in the complex X not already included in a prior element A.sub.i and adjacent a 2-cell c.sup.2.sub.j in the sub-complex X.sub.k ;
• f) testing whether adding the 2-cell c.sup.2.sub.j selected in step e) and all 1-cells and 0-cells incident thereto to the sub-complex X.sub.k would cause the sub-complex X.sub.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.sup.2.sub.j tested in step f) to register A.sub.k and adjoining this 2-cell c.sup.2.sub.j and all its incident 1-cells and 0-cells to keep the sub-complex X.sub.k a closed set;
• i) returning to step e);
• j) since element A.sub.k and sub-complex X.sub.k are complete, adding element A.sub.k to a register P storing the partition P and storing the sub-complex X.sub.k ;
• and
• k) going to step b) if there remains any 2-cell c.sup.2.sub.j in some element A.sub.i.

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).

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).

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.