[ai-geostats] SUM: Optimization of monitoring networks
- Dear list,
Thanks a lot for the many replies to my query on how to distribute
points in a complex area in an optimal way.
A few of you gave me a list of papers on network optimization that do
not reply to my question as these take into account the spatial
correlation of the monitored phenomenon. My question was about the
location of points independently of any variable and was thus somehow
To reuse Gerards' words, I want to minimise the maximum distance from
any point in the area to the nearest sampling point, not minimize the
kriging variance. An impressive review on the last topic (sampling
design + matlab codes for network optimization) can be found in Gunter
Spoeck's PhD, see http://www.math.uni-klu.ac.at/~guspoeck/book.pdf ,
(22 MB pdf).
Chapter 9 in Okabe et al. is a good reference and discusses as a case
study the optimal distribution of mailboxes in Tokyo. However, the
borders of the monitored area are defined as a rectangle, which
simplifies greatly the problem.
Another reference (see end of mail) given to me seems to be more
appropriate for what I am looking for. Still have to read it properly
but it is very much related to what I am looking for (here, its is about
the distrubution of siren locations). Thanks Morton !
From Jeffrey W. Lively, I received the following suggestions:
- Visual Sample Plan (VSP). It is maintained by Battelle for the DOE's
Pacific Northwest National Laboratory in Washington State.
It has an algorithm that they call adaptive fill which is designed to
suggest to you the optimal spatial location to place additional samples.
- SADA. It has comparable adaptive fill algorithms and can suggest
sample placement based on reducing the amount of uncertainty in addition
to simple geometric considerations. It is developed and maintained by
the University of Tennessee and is available for download from the web.
Very useful (thanks to jeolson@... for that!) is the
following resource: http://www.faqs.org/faqs/graphics/algorithms-faq/
In addition to Roderick's reference "Spatial tessellations: Concepts and
applications of Voronoi diagrams", by Atsuyuki Okabe and Barry Boots and
Kokichi Sugihara and Sung Nok Chiu. Published by Wiley, NYC (2000),
worth to mention are:
Papers in Regional Science
Volume 83 Page 565 - July 2004
Volume 83 Issue 3
A lattice covering model for evaluating existing service facilities
Morton E. O'Kelly, Alan T. Murray
Abstract. This article presents the following location problem: align a
regularly spaced grid of new facilities as well as possible with a set
of existing centres. The problem has some similarity to a problem in
classical central place theory, namely the spatial arrangement of
services with a particular range of coverage. The article poses the
problem, gives a non-linear formulation, and details solution
approaches. A robust heuristic, based on geometric insights, is also
devised: if the basis for the new grid is centred on at least one fixed
centre, an enumeration of various rotation angles will be effective for
finding local minima (and maxima). As a practical application of this
problem, a region may wish to supplement an existing system of fixed
siren locations with additional facilities in such a way as to fill in,
or complete, the partial coverage pattern. An evaluation of the siren
system in Dublin, OH, USA, is utilised to demonstrate the effectiveness
of the technique.
2 other references provided by Dan Bebber are:
Button J et al. 1996. Mobile network design and optimisation. British
Telecom Technology Journal 14:29-46
G. W. Wiskin, R. G. Manton and J. H. Causebrook 1992. Masts, Antennas
and Service Planning, Focal Press.
I did not list other references I received on monitoring network
optimization for groundwater, rainfall, etc. modelling as these are not
directly linked to my question.
Thanks to all for the replies and discussions !
Gregoire Dubois (Ph.D.)
European Commission (EC)
Joint Research Centre (JRC)
Institute for Environment and Sustainability (IES)
TP 441, Via Fermi 1
21020 Ispra (VA)
Tel. +39 (0)332 78 6360
Fax. +39 (0)332 78 5466
"The views expressed are purely those of the writer and may not in any
circumstances be regarded as stating an official position of the