home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2765 < prev    next >
Encoding:
Internet Message Format  |  1992-12-30  |  1.5 KB
  1. Path: sparky!uunet!portal!cup.portal.com!lordSnooty
  2. From: lordSnooty@cup.portal.com (Andrew - Palfreyman)
  3. Newsgroups: comp.theory
  4. Subject: Optimisation Problem With Groups
  5. Message-ID: <72618@cup.portal.com>
  6. Date: Wed, 30 Dec 92 06:48:13 PST
  7. Organization: The Portal System (TM)
  8. Distribution: world
  9. Lines: 29
  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. | lord snooty @the giant |  Would You Like Space Potatoes With That?       |
  38. | poisoned electric head |              andrew_-_palfreyman@cup.portal.com |
  39.  --------------------------------------------------------------------------
  40.