NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/ai/3261

Text File | 1992-08-29 | 3.2 KB | 86 lines

Newsgroups: comp.ai
Path: sparky!uunet!secapl!Cookie!frank
From: [e-mail] (Frank Adams)
Subject: Re: regions within regions
Message-ID: <[e-mail]>
Date: Fri, 28 Aug 1992 21:14:28 GMT
References: <[e-mail]> <[e-mail]>
Organization: Security APL, Inc.
Lines: 75

In article <[e-mail]> [e-mail] (Stephen M Jameson) writes:
>In article <[e-mail]> [e-mail] (Paul Singleton) writes:
>> I have some regions in N-space, each defined by a simple set of constraints,
>> e.g.
>>     0 =< X =< 5         (1)
>>     0 =< Y =< 5         (2)
>>     2 =< Z =< 7         (3)
>>     0 =< X+Y =< 8       (4)
>>
>> and I need an algorithm (for general N) to determine whether one region
>> completely encloses another.
>
>This is based on about 5 minutes of pen-pushing, so it may need some smoothing
>of the rough edges, but your algorithm will be based on the following three
>facts:
>
>1.    Any pair of constraints on different dimensions:
>
>>     0 =< X =< 5        (1)
>>     0 =< Y =< 5        (2)
>
>Implies a constraint on their sum, which is well defined because of the
>limits your problem imposes on definition of the constraints.  In this case, we
>have:
>
>    0 =< X + Y =< 10   (5)
>
>2.    Any two constraints:
>
>    a =< X =< b
>    c =< X =< d
>
>where X is a single dimension or a sum of dimensions, can be replaced by:
>
>    max(a,c) =< X =< min(b,d)
>
>Thus while constraints (1) and (2) above imply constraint (5), combining
>constraints (4) and (5) by the formula above gives constraint (4), i.e.
>constraint (4) is "tighter than" or "subsumes" (5).  Thus given any set of
>constraints on dimensions, you can eliminate duplicate constraints on the same
>dimension or sum of dimensions.
>
>3.    A region A defined by a set of constraints {a_i} is completely enclosed by
>another region B defined by {b_i} if and only if:
>
>    a.    All of the dimensions (including sums of dimensions), which are
>        constrained {b_i} are also constrained by {a_i}.
>
>    b.    For each constraint in {b_i}, the constraint in {a_i} constraining the
>        same dimension or sum of dimensions must be "tighter than" the
>        constraint in {b_i}.
>
>Thus we have the following general algorithm:
>
>Given a set of dimensions {X1, X2, .. Xn}, and two sets of constraints,
>{a_i} and {b_i}, where each constraint is of the form:
>
>    k1_i <= X_i_1 + ... + X_i_n <= k2_i             (n may be 1)
>
>Step 1.    For each set, using observation 1 above, generate all possible
>constraints on sums of dimensions.
>
>Step 2.    For each set, using observation 2 above, eliminate all duplicate
>constraints in each set.
>
>Step 3.    For each constraint in {b_i}, verify that there is a constraint in
>{a_i} which constrains the same dimension or sum of dimensions and is "tighter
>than" the constraint in {b_i}.  If this is the case for all constraints in
>{b_i}, then the region defined by {a_i} is completely enclosed by {b_i}.
>
>Each step is fairly straightforward, so I won't generate pseudo-code here.
>
Since nobody else has done so, let me note that this is *not* a solution, or
even much of a start at a solution.  This is a "linear programming" problem;
accept no substitutes.