In this paper, we present and evaluate a Voronoi method for partitioning continuous information spaces. We define the formal characteristics of the problem and discuss several well-known partitioning methods and approaches. We submit that although they all partially solve the problem, they all have shortcomings. As an alternative, we offer an approach based on an adaptive version of the multiplicatively weighted Voronoi diagram. The diagram is ‘adaptive’ because it is computed backwards; that is, the generators' weights are treated as dependent rather than independent variables. We successfully test this adaptive solution using both ideal-typical (artificial) and empirical data. Since the resultant visualizations are meant to be used by human subjects, we then discuss the results of a usability experiment, positioning the adaptive solution against a commonly used rectangular solution and the classic nonweighted Voronoi solution. The results indicate that in terms of usability, both the rectangular and the adaptive Voronoi solution outperform the standard Voronoi solution. In addition, although subjects are better able to gage rectangular area relationships, only the adaptive Voronoi solution satisfies all geometric constraints of weight-proportional partitioning.
SkupinA. A cartographic approach to visualizing conference abstracts. IEEE Computer Graphics and Application2002; 22: 50–58.
8.
HöökK.BenyonD.MunroA.J., (Eds.), Designing Information Spaces: The Social Navigation Approach. Series: Computer Supported Cooperative Work. Springer-Verlag: London, UK, 2003.
9.
WiseJAThomasJJPennockKLantripDPottierMCrowASchurV. Visualizing the non-visual: spatial analysis and interaction with information from text documents. Proceedings InfoVis 1995. IEEE Symposium on Information Visualization.IEEE: New York, NY, 1995; 51–58.
10.
CouclelisH. Worlds of information: The geographic metaphor in the visualization of complex information. Cartography and Geographic Information Systems1998; 25: 209–220.
11.
SkupinA. From metaphor to method: cartographic perspectives on information visualization. RothSFKeimDA (Eds). Proceedings IEEE Symposium on Information Visualization (InfoVis).IEEE Computer Society: Los Alamitos, CA, 2000; 91–97.
12.
SkupinA. On geometry and transformation in map-like information visualization. In: BörnerK.ChenC, editors. Visual interfaces to digital libraries. Lectures in Computer Science, vol. 2539. Springer-Verlag: Berlin, 2002; 161–170.
13.
FabrikantSIButtenfieldBP. Formalizing semantic spaces for information access. Annals of the Association of American Geographers2001; 91: 263–280.
14.
PeuquetDJKraakMJ. Geobrowsing: Creative thinking and knowledge discovery using geographic visualization. Information Visualization2002; 1: 80–91.
15.
HallSS. Mapping the Next Millennium: The Discovery of New Geographies.Random House: New York, NY, 1992.
16.
TufteER. The Visual Display of Quantitative Information.Graphics Press: Cheshire, CT, 1983.
SkupinA. (1998) Organizing and visualizing hypermedia information space. Doctoral Dissertation, Department of Geography, State University of New York at Buffalo.
19.
BrulsMHuizingKvan WijkJJ. Squarified treemaps. Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization, IEEE Computer Society: Silver Spring, MD, 2000; 33–42.
20.
JohnsonBShneidermanB. Tree-maps: a space-filling approach to the visualization of hierarchical information structures. Proceedings of IEEE Visualization 91, IEEE: New York, 1991; 284–291.
21.
ShneidermanB. Tree visualization with tree maps: A 2-d Spacefilling Approach. ACM Transactions on Graphics1992; 11: 92–99.
22.
ChenHHoustonALSewellRRSchatzBR. Internet browsing and searching; user evaluations of category map and concept space techniques. Journal of the American Society for Information Science1998; 49: 582–608.
23.
ChenHSchuffelsCOrwigR. Internet categorization and search: A self-organizing approach. Journal of Visual Communication and Image Representation1996; 7: 88–102.
24.
KaskiSHonkelaTLagusKKohonenT. WEBSOM: Self-organizing maps of document collections. Neurocomputing1998; 21: 101–117.
LinXSoergelDMarchioiniG. A self-organizing semantic map for information retrieval. Proceedings of the 14th Annual International ACM/SIGIR Conference on Research and Development in Information Retrieval, ACM: Chicago, IL, 1991; 262–269.
27.
LinCChenHNunamakerJF. Verifying the proximity and size hypothesis for self-organizing maps. Journal of Management Information Systems.2000; 16: 57–70.
28.
AndrewsKKienreichWSabolVBeckerJDroschlGKappeFGranitzerMAuerPTochtermannK. The InfoSky Visual Explorer: Exploiting hierarchical structure and document similarities. Information Visualization2002; 1: 166–181.
29.
OkabeABootsBSugiharaKChiuSN. Spatial Tesselations Concepts and Applications of Voronoi Diagrams.Wiley & Sons: Chichester, UK, 2000.
30.
MukherjeaSHaraY. Focus+context views of world-wide web nodes. Proceedings of Hypertext 97, ACM Press: New York, 1997; 187–196.
31.
TrubinS. Information space mapping with adaptive Voronoi Diagrams. Master Thesis, Department of Computer Science, Oregon State University: Corvallis, OR, 2006.
32.
DentBD. Cartography: Thematic Map Design.Wm. C. Brown Publishers: Dubuque, IA, 1990.
33.
ToblerW. Thirty five years of computer cartograms. Annals of the Association of American Geographers2004; 94: 58–73.
34.
VoronoiGF. Nouvelles applications des paramètres continus à la théorie des formes quadratiques Premier Mémoire: Sûr quelques propriétés des formes quadratiques positives parfaits. Journal für die Reine und Angewandte Mathematik1907; 133: 97–178.
35.
VoronoiGF. Nouvelles applications des paramètres continus à la théorie des formes quadratiques Deuxième Mémoire: Recherches sûr les parallélloèdres primitives. Journal für die Reine und Angewandte Mathematik1908; 134: 198–287.
36.
VoronoiGF. Nouvelles applications des paramètres continus à la théorie des formes quadratiques Deuxième Mémoire: Recherches sûr les parallélloèdres primitives, Second partie: Domaines de formes quadratiques correspondant aux différent types de parallélloèdres primitives. Journal für die Reine und Angewandte Mathematik1909; 136: 67–181.
37.
MuLan. Polygon characterization with the multiplicatively weighted Voronoi diagram. Professional Geographer2004; 59: 223–239.
38.
DurellCV. Modern Geometry: The Straight Line and Circle. Macmillan: London, 1928.
39.
OgilvyCS. Excursions in Geometry.Dover: New York, NY, 1990.
40.
AurenhammerF. Voronoi Diagrams – a Survey. Report 263. Institute for Information Processing. University of Graz: Graz, Austria, 1988.
41.
ReitsmaRTrubinSSethiaS. Information space regionalization using adaptive multiplicatively weighted Voronoi diagrams. BanissiEBörnerKChenCDastbazMClapworthyGFaiolaAIzquierdoEMapleCRobertsJMooreCUrsynAZhangJ (Eds). Proceedings of the Eight International Conference on Information Visualization IV 2004, IEEE Computer Society: Los Alamitos, CA, 2004; 290–293.
42.
CarlsonLEReitsmaRFBrandemuehlMJHertzbergJRSullivanJFGabbardSG. Exploiting an engineering building as a unique distance learning tool. International Journal of Engineering Education2003; 19: 379–388.
43.
ButtenfieldBPReitsmaRF. Loglinear and multidimensional scaling models of internet transactions. International Journal of Human-Computer Studies2002; 57: 101–119.
44.
ReitsmaRThabaneLMacleodM. Spatialization of web sites using a weighted frequency model of navigation data. Journal of the American Society for Information Systems and Technology2004; 55: 13–22.
45.
MulletKSanoD. Designing Visual Interfaces: Communication Oriented Technique.Prentice-Hall: Mountain View, CA, 1995.
46.
WertheimerM. Untersuchungen zur Lehre von Gestalt. Psychologische Forschung1923; 4: 301–350 Reprinted in part In: W.D. Ellis, (Ed) (1950). A Sourcebook of Gestalt Psychology. Humanities Press: New York, NY, 1923, 71–88.
47.
WertheimerM. Principles of perceptual organization. BeardsleeDSWertheimerM (Eds). Readings in Perception.Van Nostrand-Reinhold: Princeton, NJ, 1923; 115–137.
48.
WertheimerM. Laws of organization in perceptual forms. Psychologische Forschung1923; 4: 301–350 Reprinted in: Ellis, W.D. (Ed. and Transl.) (1938). A Source Book of Gestalt Psychology. Harcourt Brace: New York, NY, 1923; 71–88.
49.
FlanneryJJ. The relative effectiveness of some common graduated point symbols in the presentation of quantitative data. Canadian Cartographer1971; 8: 96–109.
50.
ChangKT. Visual Estimation of Graduated Circles. The Canadian Cartographer1977; 14: 130–138.
51.
StevensJ.C. A comparison of ratio scales for the loudness of white noise and the brightness of white light. PhD thesis, Harvard University, Cambridge, MA, 1957.
52.
WilliamsRL. Statistical Symbols for Maps; Their Design and Relative Values.Map Laboratory: Yale University, New Haven, CO, 1956.
53.
CrawfordPV. Perception of grey-tone symbols. Annals of the Association of American Geographers1971; 61: 721–735.
54.
CrawfordPV. The perception of graduated squares as cartographic symbols. Cartographic Journal1973; 10: 85–88.
55.
CoxCW. Anchor effects and the estimation of graduated circles and squares. American Cartographer1976; 3: 65–74.
56.
GroopREColeD. Overlapping graduated circles, magnitude estimation and method of portrayal. Canadian Cartographer1978; 15: 114–122.
