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