home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.ai
- Path: sparky!uunet!secapl!Cookie!frank
- From: frank@Cookie.secapl.com (Frank Adams)
- Subject: Re: regions within regions
- Message-ID: <1992Sep02.224347.161452@Cookie.secapl.com>
- Date: Wed, 02 Sep 1992 22:43:47 GMT
- References: <SJAMESON.92Aug13083908@fergie.atl.ge.com> <1992Aug28.211428.148200@Cookie.secapl.com> <22948@ilog.fr>
- Organization: Security APL, Inc.
- Lines: 60
-
- In article <22948@ilog.fr> lepape@ilog.UUCP (Claude Le Pape) writes:
- >
- >In article <1992Aug28.211428.148200@Cookie.secapl.com> frank@Cookie.secapl.com
- >(Frank Adams) writes:
- >
- >> In article <SJAMESON.92Aug13083908@fergie.atl.ge.com> sjameson@atl.ge.com
- >(Stephen M Jameson) writes:
- >
- >>> In article <3753@keele.keele.ac.uk> csa09@seq1.keele.ac.uk (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:
- >>> ...
- >
- >> 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.
- >
- >Even though I ---in this particular case--- agree with the
- >conclusion, I am afraid the sententious sentence above (This is a
- >"linear programming" problem; accept no substitutes) does not provide
- >very valuable information to Paul Singleton. Of course his problem IS
- >a LINEAR problem, but there are many particular types of linear
- >problems for which a general linear programming algorithm is not the
- >most appropriate (e.g., critical path problems).
-
- Yes, it's true that there may be other information not given which would
- enable simplification. However, no such information was given; I replied to
- the problem as stated.
-
- >The problem that P. Singleton wants to solve seemingly has an important
- >characteristic: all the coefficients of variables are equal to 1. This
-
- I assumed that this was merely a case of providing relatively simple
- examples. I don't think that the assumption that it is true in general
- is justified.
-
- >may suggest that an efficient algorithm ---more efficient than general
- >linear programming--- exists or may exist for such a problem. In fact
- >it happens that every linear problem with integral (or rational)
- >coefficients/constants can be rewritten as a linear problem with
- >coefficients of variables equal to 1.
- >
- >[proof omitted]
-
- This is interesting. Thank you.
-