Article View: comp.theory
Article #1692Optimisation Problem With Groups
From: Andrew - Palfreyman
Date: Wed, 30 Dec 1992 14:48
Date: Wed, 30 Dec 1992 14:48
29 lines
1615 bytes
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!lordSnootyShow 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