home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18627 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  1.3 KB
  1. Path: sparky!uunet!portal!cup.portal.com!lordSnooty
  2. From: lordSnooty@cup.portal.com (Andrew - Palfreyman)
  3. Newsgroups: sci.math
  4. Subject: Help needed - Constraints Problem
  5. Message-ID: <74114@cup.portal.com>
  6. Date: Thu, 21 Jan 93 19:20:59 PST
  7. Organization: The Portal System (TM)
  8. Distribution: world
  9. Lines: 27
  10.  
  11. I am interested in finding an efficient algorithm for solving
  12. the following problem:
  13.  
  14. System
  15. ------
  16. A bounded Euclidean 2-D surface with discrete coordinates (0<=x<=XMAX,
  17. 0<=y<=YMAX) is assigned numbers z(x,y) at each point. Nothing is known 
  18. _a priori_ about this assignment. The range of z (0<=z<=ZMAX) is far
  19. higher than the total number of points; 
  20.     i.e. XMAX*YMAX / (dx*dy) << ZMAX/dz, where d(i) is the granularity.
  21.  
  22. Problem
  23. -------
  24. Given a fixed range of z-values RZ (RZ > dz), the problem is:
  25. group contiguous points within the range such that, after covering
  26. every point on the surface, the final grouping minimises the total 
  27. number of groups.
  28.  
  29. Notes
  30. -----
  31. * "Contiguous" is taken to mean +/- dx or dy of the point under
  32.   consideration, but not both (i.e. no diagonal connections).
  33. * The minimum size of a group is one point.
  34. * Note that RZ is a range = zmax-zmin, and we are free to choose the
  35.   absolute value of one of {zmax, zmin} for any group.
  36. ---
  37. Andrew Palfreyman
  38.