home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / 3097 < prev    next >
Encoding:
Internet Message Format  |  1992-08-14  |  3.6 KB
  1. Path: sparky!uunet!crdgw1!ge-dab!puma.ATL.GE.COM!puma!sjameson
  2. From: sjameson@atl.ge.com (Stephen M Jameson)
  3. Newsgroups: comp.ai
  4. Subject: Re: regions within regions
  5. Message-ID: <SJAMESON.92Aug13083908@fergie.atl.ge.com>
  6. Date: 13 Aug 92 12:39:08 GMT
  7. References: <3753@keele.keele.ac.uk>
  8. Sender: news@puma.ATL.GE.COM (USENET News System)
  9. Organization: General Electric Advanced Technology Labs
  10. Lines: 84
  11. In-Reply-To: csa09@seq1.keele.ac.uk's message of 10 Aug 92 15:22:41 GMT
  12.  
  13. In article <3753@keele.keele.ac.uk> csa09@seq1.keele.ac.uk (Paul Singleton) writes:
  14. > I have some regions in N-space, each defined by a simple set of constraints,
  15. > e.g.
  16. >     0 =< X =< 5         (1)
  17. >     0 =< Y =< 5         (2)
  18. >     2 =< Z =< 7         (3)
  19. >     0 =< X+Y =< 8       (4)
  20. > 
  21. > and I need an algorithm (for general N) to determine whether one region
  22. > completely encloses another.
  23.  
  24. This is based on about 5 minutes of pen-pushing, so it may need some smoothing
  25. of the rough edges, but your algorithm will be based on the following three
  26. facts:
  27.  
  28. 1.    Any pair of constraints on different dimensions:
  29.  
  30. >     0 =< X =< 5        (1)
  31. >     0 =< Y =< 5        (2)
  32.  
  33. Implies a constraint on their sum, which is well defined because of the
  34. limits your problem imposes on definition of the constraints.  In this case, we
  35. have:
  36.  
  37.     0 =< X + Y =< 10   (5)
  38.  
  39. 2.    Any two constraints:
  40.  
  41.     a =< X =< b
  42.     c =< X =< d
  43.  
  44. where X is a single dimension or a sum of dimensions, can be replaced by:
  45.  
  46.     max(a,c) =< X =< min(b,d)
  47.  
  48. Thus while constraints (1) and (2) above imply constraint (5), combining
  49. constraints (4) and (5) by the formula above gives constraint (4), i.e.
  50. constraint (4) is "tighter than" or "subsumes" (5).  Thus given any set of
  51. constraints on dimensions, you can eliminate duplicate constraints on the same
  52. dimension or sum of dimensions.
  53.  
  54. 3.    A region A defined by a set of constraints {a_i} is completely enclosed by
  55. another region B defined by {b_i} if and only if:
  56.  
  57.     a.    All of the dimensions (including sums of dimensions), which are
  58.         constrained {b_i} are also constrained by {a_i}.
  59.  
  60.     b.    For each constraint in {b_i}, the constraint in {a_i} constraining the
  61.         same dimension or sum of dimensions must be "tighter than" the
  62.         constraint in {b_i}.
  63.  
  64. Thus we have the following general algorithm:
  65.  
  66. Given a set of dimensions {X1, X2, .. Xn}, and two sets of constraints,
  67. {a_i} and {b_i}, where each constraint is of the form:
  68.  
  69.     k1_i <= X_i_1 + ... + X_i_n <= k2_i             (n may be 1)
  70.  
  71. Step 1.    For each set, using observation 1 above, generate all possible
  72. constraints on sums of dimensions.
  73.  
  74. Step 2.    For each set, using observation 2 above, eliminate all duplicate
  75. constraints in each set.
  76.  
  77. Step 3.    For each constraint in {b_i}, verify that there is a constraint in
  78. {a_i} which constrains the same dimension or sum of dimensions and is "tighter
  79. than" the constraint in {b_i}.  If this is the case for all constraints in
  80. {b_i}, then the region defined by {a_i} is completely enclosed by {b_i}.
  81.  
  82. Each step is fairly straightforward, so I won't generate pseudo-code here.
  83.  
  84.  
  85.  
  86.         
  87. --
  88. Steve Jameson                           General Electric Aerospace 
  89. sjameson@atl.ge.com                     Advanced Technology Laboratories
  90.                                         Moorestown, New Jersey              
  91. ****************************************************************************
  92. **  . . . but I do not love the sword for its sharpness, nor the arrow    **
  93. **  for its swiftness, nor the warrior for his glory.  I love only that   **
  94. **  which they defend . . .                                               **
  95. **    -- Faramir, "The Two Towers"                                        **
  96. ****************************************************************************
  97.