home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9507 < prev    next >
Encoding:
Internet Message Format  |  1992-07-24  |  2.0 KB
  1. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!jvnc.net!netnews.upenn.edu!netnews.cc.lehigh.edu!ns1.cc.lehigh.edu!fc03
  2. From: fc03@ns1.cc.lehigh.edu (Frederick W. Chapman)
  3. Newsgroups: sci.math
  4. Subject: Re: Lattice points in a polytope? (How to find all of them?)
  5. Message-ID: <1992Jul24.132125.155015@ns1.cc.lehigh.edu>
  6. Date: 24 Jul 92 13:21:25 GMT
  7. Organization: Lehigh University
  8. Lines: 41
  9.  
  10. In article <BruKLH.DBz@watdragon.waterloo.edu>, xjzhu@jeeves.waterloo.edu 
  11. (Xiao Jun Zhu) writes:
  12.  
  13. >Hi, there:
  14. >
  15. >   I am in need of an efficient program or algorithm(prefer in C) which can 
  16. >find all the integer points in a polytope defined by sets of inequalities.
  17. >(Suppose that I know that the number of lattice points is not so huge.)
  18. >If you know such a thing exists, please send a message to me. Thanks very
  19. >much for your help.
  20. >
  21. >Regards, Xiaojun.
  22.  
  23. When you find your program, you might want to try it on the following
  24. simple test case:  Let S be the simplex (the simplest example of a convex
  25. polytope) defined by the inequalities
  26.  
  27.                        x_i >= 0 for i = 1, 2,..., n
  28.                         x_1 + x_2 + ... + x_n <= M
  29.  
  30. where n is a positive integer, and M is a non-negative integer.  The number
  31. of integer lattice points inside S is given by the binomial coefficient
  32.  
  33.                                 ( M+n )
  34.                                 (     )
  35.                                 (  n  )
  36.  
  37. which is an n-th degree polynomial in M.
  38.  
  39. ...........................................................................
  40.  
  41. Pardon my boyish exuberence, but I think this a nifty fact.  How does one
  42. go about proving this -- by induction on M?
  43.  
  44. -- 
  45.  
  46. o ------------------------------------------------------------------------- o
  47. |  Frederick W. Chapman, User Services, Computing Center, Lehigh University |
  48. |    Campus Phone:  8-3218     Preferred E-mail Address:  fc03@Lehigh.Edu   | 
  49. |  "I do comedy and magic; what you don't find funny -- that's the magic."  |
  50. o ------------------------------------------------------------------------- o
  51.