Systems for solving spatial reasoning problems via topological inference

• US 5,784,540 A
• Filed: 03/08/1996
• Issued: 07/21/1998
• Est. Priority Date: 03/08/1996
• Status: Expired due to Fees

• Current Assignee: Ecole Polytechnique Federal de Lausanne
• Original Assignee: Ecole Polytechnique Federal de Lausanne
• Inventors: Faltings, Boi
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US08/614,831
• Time in Patent Office: 865 Days
• Field of Search: 364/461, 395/51, 395/10
• US Class Current: 706/46
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 2111/12 Symbolic schematics
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

New methods of manipulating topological regions and properties have been discovered. These novel methods simplify complex spatial design problems. In some cases, the methods provide solutions or outputs where prior techniques fail entirely. Prior methods of reasoning about relations in two-dimensional space require computation with exact geometry even when only topological answers are required. For example, computing which sets of two-dimensional regions have simultaneous intersections would require explicitly constructing these intersections. These techniques become unnecessarily complex when regions have complex shapes. The present invention includes methods where topological properties of a set of regions in two-dimensional space can be manipulated by applications of topological computations. Two classes of these methods select and determine maximal and minimal simultaneous region intersections. A third method class produces sets of geometrical minimal paths satisfying a particular rule base through predetermined topological regions. The newly devised methods are much simpler and more robust than geometric methods as they do not require the exact shapes of regions to be completely known. In addition, the newly devised methods do not incur a penalty for complex curved shapes such as may occur in nature.

Claims

1. Methods of determining spatial manipulations and properties by applying topological inference techniques to spatial elements, the method being implemented in a programmed computer comprising a processor, a data storage system, at least one input device, and at least one output device, the method comprising the steps of:

(a) generating input data for the programmed computer in the form of a hypergraph, the data being related to a set of physical elements, each element being multi-dimensional wherein,

i) said elements having properties including at least;

a closed path periphery, an interior portion, and an exterior portion,

ii) any two or more elements having additional properties said properties including;

a simply connected pairwise intersection, a triple intersection, three-adjacent edges, element intersections, and element unions,

iii) the set further having properties, said properties including;

a closed path periphery, element intersections, element unions;

(b) inputting the generated input data into the programmed computer through at least one input device for storage in the data storage system;

(c) applying, to the generated input data stored in the data storage system, by means of the programmed computer,

i) an ordering step to sort pairwise intersections,

ii) a reverse elimination step which eliminates pairwise intersections in that order and finds all maximal simultaneous intersections; and

(d) applying resultant data to at least one of the output devices.

2. Methods of claim 1 where determining spatial manipulations and properties is particularly determining maximal intersections, and

said ordering step to sort pairwise intersections is further defined as:

space="preserve" listing-type="tabular">______________________________________ Function order(P,T) for all p ε

P do label (p) ←

{} j ←

|P| repeat p ←

pair ε

P with the lexicographically highest label σ

(j) ←

p P ←

P - p for all x in P do begin if three-adj (x,p,T) then label (x) ←

label (x) ∪

(j) j ←

j - 1 end until P is empty return σ

end Function three-adj (x,y,T) bits ←

x ∪

y when every subset {X.sub.1 X.sub.2 X.sub.3 .OR right. bits} ε

T then return true else return false end Function lex-greater(11

     12) while (first(11) = first(12)) and (11 ≠

{}) and (12 ≠

{}) do begin 11 ←

rest(11) 12 ←

rest(12) end if 11 ≠

{} then if 12 ≠

{} then if (first(11) >

first(12)) then return(true) else return(false) else return (true) else return(false), ______________________________________

and

said reverse elimination step to eliminate pairwise intersections is further defined as;

space="preserve" listing-type="tabular">______________________________________ Function eliminate(P,T,σ

) C ←

{} For j ←

1 to σ

do begin p ←

σ

(j) c ←

{r | (∃

×

ε

P) three-adj (x,p,T) (r ε

x)} if there does not exist d ε

C such that d .OR left. c C ←

C + c T ←

T - {t|t .OR left. p } end return C. ______________________________________

3. Methods of claim 1 where `determining spatial manipulations and properties` is more particularly determining maximal intersection information related to uses of terrain regions in accordance with physical attributes of a set of regions.

4. Methods of claim 1 where `determining spatial manipulations and properties` is more particularly determining maximal intersection information related to radio transmitter frequency allocation in accordance with physical attributes of transmitters as they may relate to a set of regions.

5. Methods of claim 1 where "determining spatial manipulations and properties" is particularly determining minimal intersections, and step c) is further comprised:

iii) determine possible minimal intersection candidates in a `generate candidates` step;

iv) determine set of regions which overlaps each candidate;

v) determine number of components in the overlap;

vi) determine difference in rank between first and zeroth homology groups;

vii) determine minimal intersections.

6. Methods of claim 5 wherein:

step i) is further defined by;

space="preserve" listing-type="tabular">______________________________________ Function order2 (P,T) j ←

|p| for all p ε

P do begin p-label (p) ←

{} s-label (p) ←

{} end repeat p ←

pair in P with the lexicographically highest p-label, where ties are broken in favor of the highest s-label P ←

P - p σ

(j) ←

p for all x in P do begin if three-adj (x,p,T) then begin p-label (x) ←

p-label (x) ·

∪

{j} U ←

all regions involved in x or p N ←

{} for all pairs u,v ε

U do begin if σ

.sup.{-1} ((u,v)) <

j then N ←

N ∪

σ

.sup.{1} ((u,v)) end if |N| + 2 = |U| ·

(.vertline.U|-1)/2 then begin for all n σ

N do begin s-label (x) ←

s-label (x) ∪

n end end end end j ←

j - 1 until P is empty return σ

end ______________________________________

and step iii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function min-candidates (M) cands ←

{} M1 ←

M while M1 ≠

{} do begin M2 ←

rest (M1) while M2 ≠

{} do begin M3 ←

rest (M2) while M3 ≠

{} do begin c ←

first (M1) ∩

first (M2) ∩

first (M3) if not member(c,cands) then cands ←

cands ∪

c end end end return cands ______________________________________

step iv) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function overlap (X,M) Y ←

{} For all m ε

M do if X .OR right. m then Y ←

Y ∪

m - X return Y ______________________________________

step v) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function components (X,Y,M) parts ←

{} firstpart ←

{} while Y ≠

{} do begin repeat new ←

{} for all y ε

Y do begin if ∃

p ε

firstpart such that intersects ? (X ∪

{y,p},M) then begin new ←

new ∪

y Y ←

Y - y end end firstpart ←

firstpart ∪

new until new ←

{} parts ←

parts ∪

firstpart firstpart ←

{} end return length (parts) ______________________________________

step vi) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function iterative-euler (X,Y,M,σ

) x ←

an arbitrary region in X sort y ε

Y according to σ

.sup.{-1} of edges y-x sum ←

1 while Y ≠

{} do begin f ←

first (Y) Y ←

rest (Y) sum ←

sum + components (X ∪

{f},Y,M) - 1 end return sum ______________________________________

step vii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function minimal-intersections(M,σ

) CANDS ←

min-candidates (M) ∪

{} m ←

{} For all c ε

CANDS do begin o ←

overlap(c,M) p ←

components(c,o) e ←

iterative-euler(c,o,σ

) if e + p - 1 >

0 then m ←

m ∪

c end return m. ______________________________________

7. Methods of claim 5 where `determining spatial manipulations and properties` is more particularly determining minimal intersection information related to radio transmitter frequency allocation in accordance with physical attributes of transmitters as they may relate to a set of regions.

8. Methods of claim 5 where `determining spatial manipulations and properties` is more particularly determining minimal intersection information related to uses of terrain regions in accordance with physical attributes of a set of regions.

9. Methods of claim 5 where `determining spatial manipulations and properties` is more particularly determining minimal paths, and step c) is comprised the steps:

vii) determine region sets in a minimal skeleton,

viii) determine adjacencies between sets in the minimal skeleton,

ix) map beginning and endpoint to sets in the minimal skeleton,

x) search graph defined by sets and adjacencies to determine cycle-free paths between beginning and end sets.

10. Methods of claim 9, wherein:

step i) is further defined by;

space="preserve" listing-type="tabular">______________________________________ Function order2(P,T) j ←

|P| for all p ε

P do begin p-label (p) ←

{} s-label (p) ←

{} end repeat p ←

pair in P with the lexicographically highest p-label, where ties are broken in favor of the highest s-label. P ←

P - p σ

(j) ←

p for all x in P do begin if three-adj (x,p,T) then begin p-label (x) ←

p-label (x) ∪

{j} U ←

all regions involved in x or p N ←

{} for all pairs u,v ε

U do begin if σ

.sup.{-1} ({u,v}) ≦

j then N ←

N ∪

σ

.sup.{1} ({u,v}) end if |N| + 2 = |U| ·

(.vertline.U|-1)/2 then begin for all n σ

N do begin s-label (x) ←

s-label (x) ∪

n end end end end j ←

j - 1 until P is empty return σ

end ______________________________________

and step iii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function min-candidates2 (M) cands ←

{} M1 ←

M while M1 ≠

{} do begin M2 ←

rest (M1) while M2 ≠

{} do begin c2 ←

first (M1) ∩

first (M2) if not member (c2,cands) then cands ←

cands ∪

c2 M3 ←

rest (M2) while M3 ≠

{} do begin c3 ←

c2 ∩

first (M3) if not member (c3,cands) then cands ←

cands ∪

c3 end end end return cands ______________________________________

and step vii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function path-places (C,M,σ

) places ←

{} for all c ε

C do begin σ

←

overlap (c,M) comp ←

components (c,o,M) euler ←

euler(c,o,M,σ

) f (comp ≠

     1) or (euler + comp - 1 ≠

     0) then places ←

places ∪

c end return places;

______________________________________

and step viii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function skeleton-edges (P) edges ←

{} for all p1 ε

P do if p1 .epsilon slash. m then for all p2 ε

P do if p1 .OR left. p2 and ∃

p3 ε

P (p1 .OR left. p3 .OR left. p2) then edges ←

edges ∪

(p1,p2) return edges. ______________________________________

11. Methods of claim 9 where `determining spatial manipulations and properties` is more particularly determining minimal skeleton information related to uses of terrain regions in accordance with physical attributes of a set of regions.

12. Methods of claim 9 where `determining spatial manipulations and properties` is more particularly determining minimal skeleton information related to uses for determining a preferred assembly sequence.

13. Apparatus for topological inference decision making, the system comprising:

(a) at least one input device for receiving data comprising a hypergraph, the data being related to a set of physical elements, each element being multi-dimensional wherein,

i) said elements having properties including at least;

a closed path periphery, an interior portion, and an exterior portion,

ii) any two or more elements having additional properties, said properties including;

a simply connected pairwise intersection, a triple intersection, three-adjacent edges, element intersections, and element unions,

iii) the set further having properties, said properties including;

a closed path periphery, element intersections, element unions;

(b) a computer storage system, coupled to at least one of the input devices, for storing data input into the system through at least one of the input devices;

(c) a programmable processor, coupled to the computer storage system and at least one of the input devices, for processing the input data stored in the data storage system to generate output data, in accordance with programming implementing the functions of;

i) an ordering step to sort pairwise intersections,

ii) a reverse elimination step which eliminates pairwise intersections in that order and finds all maximal simultaneous intersections, and

(d) applying the output data to at least one output device.

14. Apparatus of claim 13 where `topological inference decision making` is more particularly finding maximal intersections, and

said ordering step to sort pairwise intersections is further defined as:

space="preserve" listing-type="tabular">______________________________________ Function order (P,T) for all p ε

P do label (p) ←

{ } j ←

|P| repeat p ←

pair ε

P with the lexicographically highest label σ

(j) ←

p P ←

P - p for all x in P do begin if three-adj (x,p,T) then label (x) ←

label (x) ∪

(j) end j ←

j - 1 until P ia empty return σ

end Function three-adj (x,y,T) bits ←

x ∪

y when every subset {X.sub.1 X.sub.2 X.sub.3 .OR right. bits} ε

T then return true else return false end Function lex-greater (11

     12) while (first (11) = first(12)) and (11 ≠

{}) and (12 ≠

{}) do begin 11 ←

rest (11) 12 ←

rest (12) end if 11 ≠

{} then if 12 ≠

{} then if (first (11) >

first (12) then return (true) else return (false) else return (true) else return (false), ______________________________________

and

said reverse elimination step to eliminate pairwise intersections is further defined as;

space="preserve" listing-type="tabular">______________________________________ Function eliminate (P,T,σ

) C ←

{} For j ←

1 to σ

do begin p ←

σ

(j) c ←

{r | (∃

x ε

P) three-adj (x,p,T) .sub. (r ε

x)} if there does not exist d ε

C such that d .OR left. c C ←

C + c T ←

T - {t|t .OR left. p} end return C. ______________________________________

15. Apparatus of claim 13 where `topological inference decision making` is more particularly finding maximal intersection information related to uses of terrain regions in accordance with physical attributes of a set of regions.

16. Apparatus of claim 13 where `topological inference decision making` is more particularly finding maximal intersection information related radio transmitter frequency allocation in accordance with physical attributes of transmitters as they may relate to a set of regions.

17. Apparatus of claim 13 where "topological inference decision making" is particularly determining minimal intersections, and element c) is further comprised:

iii) determine possible minimal intersection candidates in a `generate candidates` step;

iv) determine set of regions which overlaps each candidate;

v) determine number of components in the overlap;

vi) determine difference in rank between first and zeroth homology groups;

vii) determine minimal intersections.

18. Apparatus of claim 17 wherein:

step i) is further defined by;

space="preserve" listing-type="tabular">______________________________________ Function order2 (P,T) j ←

|P| for all p ε

P do begin p-label (p) ←

{} s-label (p) ←

{} end repeat p ←

pair in P with the lexicographically highest p-label, where ties are broken in favor of the highest s-label. P ←

P - p σ

(j) ←

p for all x in P do begin if three-adj (x,p,T) then begin p-label (x) ←

p-label (x) ∪

{j} U ←

all regions involved in X or p N ←

{} for all pairs u,v ε

U do begin if σ

.sup.{-1} ((u,v)) <

j then N ←

N ∪

σ

.sup.{1} ((u,v)) end if |N| + 2 = |U| ·

(.vertline.U|-1)/2 then begin for all n σ

N do begin s-label (x) ←

s-label (x) ∪

n end end end end unti P is empty return σ

end;

______________________________________

and step iii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function min-candidates (M) cands ←

{} M1 ←

M while M1 ≠

{} do begin M2 ←

rest (M1) while M2 ≠

{} do begin M3 ←

rest(M2) while M3 ≠

{} do begin c ←

first(M1) ∩

first (M2) ∩

first(M3) if not member(c,cands) then cands ←

cands ∪

C end end end return cands ______________________________________

step iv) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function overlap (X,M) Y ←

{} For all m ε

M do if X .OR right. m then Y ←

Y ∪

m - X return Y ______________________________________

step v) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function components (X,Y,M) parts ←

{} firstpart ←

{} while Y ≠

{} do begin repeat new ←

{} for all y ε

Y do begin if ∃

p ε

firstpart such that intersects? (X ∪

{y,p},M) then begin new ←

new ∪

y Y ←

Y - y end end firstpart ←

firstpart ∪

new until new = {} parts ←

parts ∪

firstpart firstpart ←

{} end return length (parts) ______________________________________

step vi) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function iterative-euler (X,Y,M,σ

) x ←

an arbitrary region in X sort y ε

Y according to σ

.sup.{-1} of edges y-x sum ←

1 while Y ≠

{} do begin f ←

first(Y) Y ←

rest(Y) sum ←

sum + components(X ∪

(f),Y,M) - 1 end return sum ______________________________________

step vii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function minimal-intersections (M,σ

) CANDS ←

min-candidates(M) ∪

{} m ←

{} For all c ε

CANDS do begin o ←

overlap(c,M) p ←

components(c,o) e ←

iterative-euler(c,o,σ

) if e + p - 1 >

0 then m ←

m ∪

c end return m. ______________________________________

19. Apparatus of claim 17 where "topological inference decision making" is more particularly determining minimal intersection information related to radio transmitter frequency allocation in accordance with physical attributes of transmitters as they may relate to a set of regions.

20. Apparatus of claim 17 where "topological inference decision making" is more particularly determining maximal intersection information related to uses of terrain regions in accordance with physical attributes of a set of regions.

21. Apparatus of claim 17 where "topological inference decision making" is more particularly determining minimal paths, and element c) is further comprised the steps:

vii) determine region sets in a minimal skeleton,

viii) determine adjacencies between sets in the minimal skeleton,

ix) map beginning and endpoint to sets in the minimal skeleton,

x) search graph defined by sets and adjacencies to determine cycle-free paths between beginning and end sets.

22. Apparatus of claim 21, wherein

step i) is further defined by:

space="preserve" listing-type="tabular">______________________________________ Function order2 (P,T) j ←

|P| for all p ε

P do begin p-label(p) ←

{} s-label(p) ←

{} end repeat p ←

pair in P with the lexicographically highest p-label, where ties are broken in favor of the highest s-label. P ←

P - p σ

(j) ←

p for all x in P do begin if three-adj (x,p,T) then begin p-label (x) ←

p-label (x) ∪

{j} U ←

all regions involved in x or p N ←

{} for all pairs u,v ε

U do begin if σ

.sup.{-1} ((u,v)) ≦

j then N ←

N ∪

σ

.sup.{1} ((u,v)) end if |N| + 2 = (|U| ·

(.vertline.U|-1)/2 then begin for all n σ

N do begin s-label (x) ←

s-label (x) ∪

n end end end end j ←

j - 1 until P is empty return σ

end;

______________________________________

and step iii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function min-candidates2 (M) cands ←

{} M1 ←

M while M1 ≠

{} do begin M2 ←

rest (M1) while M2 ≠

{} do begin c2 ←

first(Mi) ∩

first(M2) if not member(c2,cands) then cands ←

cands ∪

c2 M3 ←

rest(M2) while M3 ≠

{} do begin c3 ←

c2 ∩

first (M3) if not member(c3,cands) then cands ←

cands ∪

c3 end end end return cands;

______________________________________

and step vii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function path-places (C,M,σ

) places ←

{} for all c ε

C do begin σ

←

overlap(c,M) comp ←

components(c,o,M) euler ←

euler(c,o,M,σ

) f (comp ≠

     1) or (euler + comp - 1 ≠

     0) then places ←

places ∪

c end return places;

______________________________________

and step viii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function skeleton-edges (P) edges ←

{} for all p1 ε

P do if p1 .epsilon slash. m then for all p2 ε

P do if p1 .OR left. p2 and ∃

p3 ε

P (p1 .OR left. p3 .OR left. p2) then edges ←

edges ∪

(p1,p2) return edges. ______________________________________

23. Apparatus of claim 21 where "topological inference decision making" is more particularly determining minimal skeleton information related to uses of terrain regions in accordance with physical attributes of a set of regions.

24. Apparatus of claim 21 where "topological inference decision making" is more particularly determining minimal skeleton information related to uses for determining a preferred assembly sequence.

25. An article of manufacture comprising:

A computer usable medium having computer readable program code means embodied therein for causing topological inference decision making, the computer readable program code means in said article of manufacture comprising;

a) computer readable program code means for causing the computer to receive data related to a set of physical elements, each element being multidimensional wherein,

i) said elements having properties including at least;

a closed path periphery, an interior portion, and an exterior portion,

ii) any two or more elements having additional properties, said properties including;

a simply connected pairwise intersection, a triple intersection, three-adjacent edges, element intersections, and element unions,

iii) the set further having properties, said properties including;

a closed path periphery, element intersections, element unions;

b) computer readable program code means for causing the computer to effect

i) an ordering step to sort pairwise intersections,

ii) a reverse elimination step which eliminates pairwise intersections in that order and finds all maximal simultaneous intersections, and

c) computer readable program code means for causing the computer to output a file having a plurality of locations containing information relating to computed topological spatial elements.

26. Articles of claim 25 where "topological inference decision making" is more particularly causing determination of maximal intersections, and

said ordering step to sort pairwise intersections is further defined as:

space="preserve" listing-type="tabular">______________________________________ Function order (P,T) for all p ε

P do label(p) ←

{} j ←

|P| repeat p ←

pair ε

P with the lexicographically highest label σ

(j) ←

p P ←

P - p for all x in P do begin if three-adj (x,p,T) then label (x) ←

label (x) ∪

{j} end j ←

j - 1 until P is empty return σ

end Function three-adj (x,y,T) bits ←

x ∪

y when every subset (X.sub.1 X.sub.2 X.sub.3 .OR right. bits} ε

T then return true else return false end Function lex-greater(11

     12) while (first(11) = first(12)) and (11 ≠

{}) and (12 ≠

{}) do begin 11 ←

rest(11) 12 ←

rest(12) end if 11 ≠

{} then if 12 ≠

{} then if (first(11) >

first(12)) then return(true) else return(false) else return(true) else return (false), ______________________________________

and

said reverse elimination step to eliminate pairwise intersections is further defined as;

space="preserve" listing-type="tabular">______________________________________ Function eliminate (P,T,σ

) C ←

{} For j ←

1 to σ

do begin p ←

σ

(j) c ←

{r |(∃

x ε

P) three-adj (x,p,T) Λ

(r ε

x)} if there does not exist d ε

C such that d .OR left. c C ←

C + c T ←

T - {t|t .OR left. p} end return C. ______________________________________

27. Articles of claim 25 where "topological inference decision making" is more particularly causing determination of maximal intersections, and maximal intersections information is particularly related to uses of terrain regions in accordance with physical attributes of a set of regions.

28. Articles of claim 25 where "topological inference decision making" is more particularly causing determination of maximal intersections, and maximal intersections information is particularly related to radio transmitter frequency allocation in accordance with physical attributes of transmitters as they may relate to a set of regions.

29. Articles of claim 25 where "topological inference decision making" is more particularly causing determination of minimal intersections, and step b) is further comprised:

iii) determine possible minimal intersection candidates in a `generate candidates` step;

iv) determine set of regions which overlaps each candidate;

v) determine number of components in the overlap;

vi) determine difference in rank between first and zeroth homology groups;

vii) determine minimal intersections.

30. Articles of claim 29 wherein:

step i) is further defined by;

space="preserve" listing-type="tabular">______________________________________ Function order2 (P,T) j ←

|P| for all p ε

P do begin p-label(p) ←

{} s-label(p) ←

{} end repeat p ←

pair in P with the lexicographically highest p-label, where ties are broken in favor of the highest s-label. P ←

P - p σ

(j) ←

p for all x in P do begin if three-adj (x,p,T) then begin p-label (x) ←

p-label (x) ∪

{j} U ←

all regions involved in x or p N ←

{} for all pairs u,v ε

U do begin if σ

.sup.{-1} ((u,v)) <

j then N ←

N ∪

σ

.sup.{1}((u,v)) end if |N|+ 2 = |U| ·

(|U|-1)/2 then begin for all n σ

N do begin s-label (x) ←

s-label (x) ∪

n end end end end j ←

j - 1 until P is empty return σ

end;

______________________________________

and step iii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function min-candidates (M) cands ←

{} M1 ←

M while M1 ≠

{} do begin M2 ←

rest(M1) while M2 ≠

{} do begin M3 ←

rest(M2) while M3 ≠

{} do begin c ←

first(M1) ∩

first(M2) ∩

first(M3) if not member(c,cands) then cands ←

cands ∪

c end end end return cands ______________________________________

step v) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function components (X,Y,M) parts ←

{} firstpart ←

{} while Y ≠

{} do begin repeat new ←

{} for all y ε

Y do begin if ∃

p ε

firstpart such that intersects? (X ∪

{y,p},M) then begin new ←

new ∪

y Y ←

Y - y end end firstpart ←

firstpart ∪

new until new = {} parts ←

parts ∪

firstpart firstpart ←

{} end return length(parts) ______________________________________

step vi) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function iterative-euler (X,Y,M,σ

) x ←

an arbitrary region in X sort y ε

Y according to σ

.sup.{-1} of edges y-x sum ←

1 while Y ≠

{} do begin f ←

first(Y) Y ←

rest(Y) sum ←

sum + components(X ∪

{f},Y,M) - 1 end return sum ______________________________________

step vii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function minimal-intersections(M,σ

) CANDS ←

min-candidates(M) ∪

{} m ←

{} For all c ε

CANDS do begin o ←

overlap(c,M) p ←

components(c,o) e ←

iterative-euler(c,o,σ

) if e + p - 1 >

0 then m ←

m ∪

c end return m. ______________________________________

31. Articles of claim 29 where "topological inference decision making" is more particularly causing determination of minimal intersection information related radio transmitter frequency allocation in accordance with physical attributes of transmitters as they may relate to a set of regions.

32. Articles of claim 29 where "topological inference decision making" is more particularly causing determination of minimal intersection information related to uses of terrain regions in accordance with physical attributes of a set of regions.

33. Articles of claim 29 "topological inference decision making" is more particularly causing determination of minimal paths, and step b) is further comprised the steps:

vii) determine region sets in a minimal skeleton,

viii) determine adjacencies between sets in the minimal skeleton,

ix) map beginning and endpoint to sets in the minimal skeleton,

x) search graph defined by sets and adjacencies to determine cycle-free paths between beginning and end sets.

34. Articles of claim 33, wherein

step i) is further defined by:

space="preserve" listing-type="tabular">______________________________________ Function order2 (P,T) j ←

|P| for all p ε

P do begin p-label (p) ←

{} s-label (p) ←

{} end repeat p ←

pair in P with the lexicographically highest p-label, where ties are broken in favor of the highest s-label. P ←

P - p σ

(j) ←

p for all x in P do begin if three-adj (x,p,T) then begin p-label (x) ←

p-label (x) ∪

{j} U ←

all regions involved in x or p N ←

{} for all pairs u,v ε

U do begin if σ

.sup.{-1} ((u,v)) <

j then N ←

N ∪

σ

.sup.{1} ((u,v)) end if |N| + 2 = |U| ·

(.vertline.U|-1)/2 then begin for all n σ

N do begin s-label(x) ←

s-label (x) ∪

n end end end end j ←

j - 1 until P is empty return σ

end ______________________________________

and step iii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function min-candidates2 (M) cands ←

{} M1 ←

M while M1 ≠

{} do begin M2 ←

rest(MI) while M2 ≠

{} do begin c2 ←

first (M1) ∩

first (M2) if not member (c2,cands) then cands ←

cands ∪

c2 M3 ←

rest(M2) while M3 ≠

{} do begin c3 ←

c2 ∩

first(M3) if not member(c3,cands) then cands ←

cands ∪

c3 end end end return cands;

______________________________________

and step vii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function path-places (C,M,σ

) places ←

{} for all c ε

C do begin σ

←

overlap (c,M) comp ←

components (c,o,M) euler ←

euler (c,o,M,σ

) f (comp ≠

     1) or (euler + comp - 1 ≠

     0) then places ←

places ∪

c end return places;

______________________________________

and step viii) is further defined by;

space="preserve" listing-type="tabular">______________________________________ function skeleton-edges (P) edges ←

{} for all p1 ε

P do if p1 .epsilon slash. m then for all p2 ε

P do if pl .OR left. p2 and ∃

p3 ε

P (p1 .OR left. p3 .OR left. p2) then edges ←

edges ∪

(p1,p2) return edges. ______________________________________

35. Articles of claim 29 where "topological inference decision making" is more particularly causing determination of minimal skeleton information related to uses of terrain regions in accordance with physical attributes of a set of regions.

36. Articles of claim 29 where "topological inference decision making" is more particularly causing determination of minimal skeleton information related to uses for determining a preferred assembly sequence.