home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / ai / 3314 < prev    next >
Encoding:
Text File  |  1992-09-02  |  2.7 KB  |  71 lines

  1. Newsgroups: comp.ai
  2. Path: sparky!uunet!secapl!Cookie!frank
  3. From: frank@Cookie.secapl.com (Frank Adams)
  4. Subject: Re: regions within regions
  5. Message-ID: <1992Sep02.224347.161452@Cookie.secapl.com>
  6. Date: Wed, 02 Sep 1992 22:43:47 GMT
  7. References: <SJAMESON.92Aug13083908@fergie.atl.ge.com> <1992Aug28.211428.148200@Cookie.secapl.com> <22948@ilog.fr>
  8. Organization: Security APL, Inc.
  9. Lines: 60
  10.  
  11. In article <22948@ilog.fr> lepape@ilog.UUCP (Claude Le Pape) writes:
  12. >
  13. >In article <1992Aug28.211428.148200@Cookie.secapl.com> frank@Cookie.secapl.com
  14. >(Frank Adams) writes:
  15. >
  16. >> In article <SJAMESON.92Aug13083908@fergie.atl.ge.com> sjameson@atl.ge.com
  17. >(Stephen M Jameson) writes: 
  18. >
  19. >>> In article <3753@keele.keele.ac.uk> csa09@seq1.keele.ac.uk (Paul Singleton)
  20. >>> writes:
  21. >
  22. >>>> I have some regions in N-space, each defined by a simple set 
  23. >>>> of constraints,
  24. >>>> e.g.
  25. >>>>     0 =< X =< 5         (1)
  26. >>>>     0 =< Y =< 5         (2)
  27. >>>>     2 =< Z =< 7         (3)
  28. >>>>    0 =< X+Y =< 8       (4)
  29. >>>> 
  30. >>>> and I need an algorithm (for general N) to determine whether one region
  31. >>>> completely encloses another.
  32. >
  33. >>>
  34. >>> This is based on about 5 minutes of pen-pushing, so it may need some
  35. >>> smoothing of the rough edges, but your algorithm will be based on
  36. >>> the following three facts:
  37. >>> ...
  38. >
  39. >> Since nobody else has done so, let me note that this is *not* a solution, or
  40. >> even much of a start at a solution. This is a "linear programming" problem;
  41. >> accept no substitutes.
  42. >
  43. >Even though I ---in this particular case--- agree with the
  44. >conclusion, I am afraid the sententious sentence above (This is a
  45. >"linear programming" problem; accept no substitutes) does not provide
  46. >very valuable information to Paul Singleton. Of course his problem IS
  47. >a LINEAR problem, but there are many particular types of linear
  48. >problems for which a general linear programming algorithm is not the
  49. >most appropriate (e.g., critical path problems).
  50.  
  51. Yes, it's true that there may be other information not given which would
  52. enable simplification.  However, no such information was given; I replied to
  53. the problem as stated.
  54.  
  55. >The problem that P. Singleton wants to solve seemingly has an important
  56. >characteristic: all the coefficients of variables are equal to 1. This
  57.  
  58. I assumed that this was merely a case of providing relatively simple
  59. examples.  I don't think that the assumption that it is true in general
  60. is justified.
  61.  
  62. >may suggest that an efficient algorithm ---more efficient than general
  63. >linear programming--- exists or may exist for such a problem. In fact
  64. >it happens that every linear problem with integral (or rational)
  65. >coefficients/constants can be rewritten as a linear problem with
  66. >coefficients of variables equal to 1.
  67. >
  68. >[proof omitted]
  69.  
  70. This is interesting.  Thank you.
  71.