[an error occurred while processing this directive]
Fields: Web Manual
Table of Contents
1. Introduction

2. Thin Plate Splines: Tps 3. Spatial Process Models: Krig 4. Simulating Random Fields (sim.rf)

5. Spatial Predictions for Large Data Sets
6. Other Fields Functions References

Printable version of Fields Manual

Back to Fields Home Page
5.1 Space-Filling Designs

As a companion to the curve and surface fitting in Fields we have found it useful to have an algorithm that will produce sets of points that are evenly distributed. A typical application is to choose a subset of observed locations to use as the knots for a reduced set of basis function (see the example above). The function cover.design is a function to accomplish this. The basic framework is to determine a subset of design points from a larger set of candidate points. The candidate points not only serve as possible design points but determine the coverage criterion. A design's quality is evaluated by how well it covers the candidate set and a design is improved by swapping a point from the candidate set with a design point that produces a smaller coverage criterion.

At this point an analogy may be helpful to explain the coverage criterion. Suppose that you are charged with locating a fixed number of convenience stores in a city. Given a particular set of store locations each resident will have a store that is closest to their home. Out of all the residents, find the one who is the farthest to their nearest store. This is the maximum over the nearest neighbor distances and a good design for the stores makes this criterion as small as possible. In words, one seeks to minimize the distance the residents must travel to their closest convenience store. The result is referred to as the minimax design.

The cover.design function has two approximations. The minimax criterion is approximated by a smoother criterion based on L_p norms. These are the P and Q arguments in the call. The defaults P=Q=32 appear to yield a good approximation to the minimax designs. The other approximation is that the coverage criterion is minimized by updating one design point at a time. For each design point one checks whether a swap with a candidate point will yield a smaller coverage criterion. If such a swap is found the swap is made: the new point is adopted as part of the design and the old design point is moved into the candidate set. This process continues until no more productive swaps can be made or the number of iterations is exceeded. This algorithm is not guaranteed to give a global minimum and so one may not obtain the optimal design solution. However, we have found this algorithm to give useful designs even if they are not the global minimizer. In general, the global minimum is difficult to find and has questionable added value over good approximate solutions.

There are several important features of the cover.design function related to the algorithm for finding the design. One can fix some points in the design. These are simply points that are not allowed to be swapped out. This is useful if one wants to build up a sequence of designs of increasing size with the smaller designs being subsets of the larger ones. The default is to use Euclidean metric to measure distance between points. Any S function that is a metric can be substituted for this choice. See the help file for an example. Finally the swapping algorithm may only consider swapping candidate points that are near neighbors of the design point. This is helpful when the candidate set is large.

Here is a simple example to thin out a random set of 2-d locations and shows how the fixed point option works.

Create 200 locations uniformly distributed in the unit square.

set.seed( 123)
cand <- matrix( runif( 200*2), ncol=2)

Now find a coverage design of 10 points

cover.design(cand, 10)-> design10

The component design10$design is the best design and design10$best.id gives the row numbers of the candidate set matrix that comprise the best design.

Check it out

plot( design10)
summary( design10)

Now add 20 more points for a total of 30

cover.design( cand, 30, fixed=design$best.id)

Here is what happened:

plot( cand, pch=".")
points( design10$design, pch="x", col=2)
points( design30$design, pch="o", col=3)

This is software for statistical research and not for commercial uses. The authors do not guarantee the correctness of any function or program in this package. Any changes to the software should not be made without the authors permission.

Last modified: Dec 21 2005   by thoar@ucar.edu