🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.theory
Article #1692

Optimisation Problem With Groups

#1692
From: Andrew - Palfreyman
Date: Wed, 30 Dec 1992 14:48
29 lines
1615 bytes
I am interested in finding an efficient algorithm for solving
the following problem:

System
------
A bounded Euclidean 2-D surface with discrete coordinates (0<=x<=XMAX,
0<=y<=YMAX) is assigned numbers z(x,y) at each point. Nothing is known 
_a priori_ about this assignment. The range of z (0<=z<=ZMAX) is far
higher than the total number of points; 
	i.e. XMAX*YMAX / (dx*dy) << ZMAX/dz, where d(i) is the granularity.

Problem
-------
Given a fixed range of z-values RZ (RZ > dz), the problem is:
group contiguous points within the range such that, after covering
every point on the surface, the final grouping minimises the total 
number of groups.

Notes
-----
* "Contiguous" is taken to mean +/- dx or dy of the point under
  consideration, but not both (i.e. no diagonal connections).
* The minimum size of a group is one point.
* Note that RZ is a range = zmax-zmin, and we are free to choose the
  absolute value of one of {zmax, zmin} for any group.
 --------------------------------------------------------------------------
| lord snooty @the giant |  Would You Like Space Potatoes With That?       |
| poisoned electric head |              andrew_-_palfreyman@cup.portal.com |
 --------------------------------------------------------------------------
Technical Details
Message-ID: <72618@cup.portal.com>
Path: arc1-ca.pugleaf.net!sparky!uunet!portal!cup.portal.com!lordSnooty

Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!portal!cup.portal.com!lordSnooty
From: lordSnooty@cup.portal.com (Andrew - Palfreyman)
Newsgroups: comp.theory
Subject: Optimisation Problem With Groups
Message-ID: <72618@cup.portal.com>
Date: Wed, 30 Dec 92 06:48:13 PST
Organization: The Portal System (TM)
Distribution: world
Lines: 29