This paper introduces procedures involving the recursive construction of Voronoi diagrams and Delaunay tessellations. In such constructions, Voronoi and Delaunay concepts are used to tessellate an object space with respect to a given set of generators and then the construction is repeated every time with a new generator set, which comprises members selected from the previous generator set plus features of the current tessellation. Such constructions are shown to provide an integrating conceptual framework for a number of disparate procedures, as well as extending the existing functionality of the basic Voronoi and Delaunay procedures to variable spatial resolutions. Further, because they are shown to be fractal in nature, it is suggested that this characteristic can be exploited in the development of new strategies for spatial modelling.
Get full access to this article
View all access options for this article.
References
1.
ChakrounHBenieG BO'NeillN TDesiletsJ, 2000, “Spatial analysis weighting using Voronoi diagrams”International Journal of Geographical Information Science14, 319–336
2.
De FlorianiL, 1989, “A pyramidal data structure for triangle-based surface description”IEEE Computer Graphics and Applications9(2) 67–78
3.
De FlorianiLPuppoE, 1992, “A hierarchical triangle-based model for terrain description”, in Theories and Methods of Spatio-temporal Reasoning in Geographic Space Eds FrankA UCampariIFormentiniU (Springer, Berlin) pp 236–251
4.
De FlorianiLPuppoE, 1995, “Hierarchical triangulation for multi-resolution surface description”ACM Transactions on Graphics14, 363–411
5.
De FlorianiLFalcidienoBPienoviC, 1985, “Delaunay-based representation of surfaces defined over arbitrarily shaped domains”Computer Vision, Graphics, and Image Processing32, 127–140
6.
De FlorianiLMarzanoPPuppoE, 1996, “Multiresolution models for terrain surface description”The Visual Computer12, 317–346
7.
DuQFaberVGunzbergerM, 1999, “Centroidal Voronoi tessellations: Applications and algorithms”SIAM Review41, 637–676
8.
GoldC M, 1991, “Problems with handling spatial data—the Voronoi approach”CISM Journal ACSGC45(1) 65–80
9.
GoldC M, 1992, “The meaning of ‘neighbour’”, in Theories and Methods of Spatio-temporal Reasoning in Geographic Space Eds FrankA UCampariIFormentiniU (Springer, Berlin) pp 221–235
10.
GoldC MCondalA R, 1995, “A spatial data structure integrating GIS and simulation in a marine environment”Marine Geodesy18, 213–228
11.
GoldC MRemmeleP RRoosT, 1997, “Voronoi methods in GIS”, in Algorithmic Foundations of Geographic Information Systems Eds Van KreveldM JNievergeltJRoosTWidmayerP (Springer, Berlin) pp 21–25
12.
GürsoyH NPatrikalakisN M, 1991, “Automated interrogation and adaptive subdivision of shape using medial axis transform”Advances in Engineering Software13(5/6) 287–302
13.
HutchinsonM FGallantJ C, 1999, “Representation of terrain”, in Geographical Information Systems: Principles, Techniques, Applications, and Management, Volume 12nd edition, Eds LongleyP AGoodchildM FMaguireD JRhindD W (John Wiley, New York) pp 105–124
14.
KirkpatrickD G, 1979, “Efficient computation of continuous skeletons”, in Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science (Institute of Electrical and Electronics Engineers, New York) pp 18–27
15.
LeeD T, 1982, “Medial axis transformation of a planar shape”IEEE Transactions on Pattern Analysis and Machine Intelligence4, 363–369
16.
MartinezV JJonesB J TDominguez-TenreiroRVan De WeygaertR, 1990, “Clustering paradigms and multifractal measures”Astrophysical Journal357, 50–61
OgniewiczR LIlgM, 1992, “Voronoi skeletons: Theory and applications”, in Proceedings of the 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Illinois (IEEE Computer Society Press, Silver Spring, MD) pp 63–69
OkabeASadahiroY, 1996, “An illusion of spatial hierarchy: Spatial hierarchy in a random configuration”Environment and Planning A28, 1533–1552
21.
OkabeABootsBSugiharaK, 1994, “Nearest neighbourhood operations with generalised Voronoi diagrams: A review”International Journal of Geographical Information Systems8, 43–71
22.
OkabeABootsBSugiharaKChiuS N, 2000Spatial Tessellations: Concepts and Applications of Voronoi Diagrams2nd edition (John Wiley, Chichester, Sussex)
23.
PerryJ N, 1995, “Spatial analysis by distance indices”Journal of Animal Ecology64, 303–314
24.
PriceM AArmstrongC G, 1997, “Hexagonal mesh generation by medial surface subdivision: Part II. Solids with flat and concave edges”International Journal for Numerical Methods in Engineering40, 111–136
25.
PriceM AArmstrongC GSabinM A, 1995, “Hexagonal mesh generation by medial surface subdivision: Part I. Solids with convex edges”International Journal for Numerical Methods in Engineering38, 3335–3359
26.
ShiWPangM Y C, 2000, “Development of Voronoi-based cellular automata—an integrated dynamic model for geographical information systems”International Journal of Geographical Information Science14, 455–474
27.
ShirriffK, 1993, “Generating fractals from Voronoi diagrams”Computations and Graphics17, 165–167
28.
ShirriffK, 1998, “Generating fractals from Voronoi diagrams”, in Chaos and Fractals Ed. PickoverC A (Elsevier Science, Amsterdam) pp 23–26
SouthRBootsB, 1999, “Relaxing the nearest centre assumption in central place theory”Papers in Regional Science78, 157–177
31.
StorbeckJ E, 1990, “Recursive procedures for the spatial structuring of Christaller hierarchies”Environment and Planning B: Planning and Design17, 85–95
32.
StoyanDStoyanH, 1994Fractals, Random Shapes and Point Fields: Methods of Geometrical Statistics (John Wiley, Chichester, Sussex)
33.
TakayasuH, 1990Fractals in the Physical Sciences (Manchester University Press, Manchester)
34.
TarnTArmstrongC G, 1991, “2D finite element mesh generation by medial axis subdivision”Advances in Engineering Software13(5/6) 313–324
35.
VoigtmannABeckerLHinrichsK, 1994, “Hierarchical surface representations using constrained Delaunay (sic) triangulations”, in Advances in GIS Research: Proceedings of The Sixth International Symposium on Spatial Data Handling (Taylor and Francis, London) pp 848–867
36.
WrightD JGoodchildM F, 1997, “Data from the deep: Implications for the GIS community”International Journal of Geographical Information Science11, 523–528
37.
ZaninettiL, 1991, “Dynamical Voronoi tessellation III. The distribution of galaxies”Astronomy and Astrophysics246, 291–300
