Gahegan, M., and Lee, I. (2000) Data structures and algorithms to support interactive spatial analysis using dynamic voronoi diagrams. Computers, Environment and Urban Systems, 24 (6). pp. 509-537.

PDF (Published Version) - Published Version Restricted to Repository staff only

Abstract

To support the need for interactive spatial analysis, it is often necessary to rethink the data structures and algorithms underpinning applications. This paper describes the development of an interactive environment in which a number of different Voronoi models of space can be manipulated together in real time to: (1) study their behaviour; (2) select appropriate models for specific analysis tasks; and (3) to examine how choice of one model over another will affect the interpretation of data. The paper studies six specific Voronoi diagram variants: the Ordinary Voronoi Diagram, the Farthest-point Voronoi Diagram, the Order-k Voronoi Diagram, the Ordered Order-k Voronoi Diagram, the kth Nearest-point Voronoi Diagram and the Multiplicatively Weighted Voronoi Diagram, and develops algorithms and data structures to store, rebuild and query these variants. From this, a generalised Voronoi data structure is proposed, from which specific Voronoi variants can be reconstructed dynamically as required. Algorithms for diagram reconstruction and for querying neighbourhood (topology or adjacency relations) of generator points and Voronoi regions are presented. An application program, developed on these ideas, is used to generate example results as proof of concept. It may be downloaded from a supporting website.

Item ID:	236
Item Type:	Article (Research - C1)
ISSN:	1873-7587
Keywords:	Voronoi diagrams, interactive spatial analysis, algorithms, data structures
Additional Information:	© 2000 Elsevier. : This journal is available online - use hypertext links above.
Date Deposited:	08 Sep 2006
FoR Codes:	08 INFORMATION AND COMPUTING SCIENCES > 0806 Information Systems @ 100%
SEO Codes:	89 INFORMATION AND COMMUNICATION SERVICES > 8902 Computer Software and Services > 890202 Application Tools and System Utilities @ 100%
Downloads:	Total: 3
	More Statistics