We use maps to navigate the physical world—what if we could also use them to navigate virtual spaces? What if the 31.5 million results from a Google search on “financial crisis” were represented as a two-dimensional map instead of a list? What would such a map look like? And how would you proportion the map to reflect the popularity or size of each document?

Associate Professor René Reitsma has been exploring these questions through his research on information space maps. “We have two dimensions on our screen, why not use them?” he asks. “Can we use some of the cartographic techniques developed over the ages to display digital information?”

Part of the answer might be found in an information visualization technique called Voronoi diagrams. In its simplest form, a Voronoi diagram partitions space around a series of points—known as generators—into regions, so that the distance from each location within a region is closer to its generator than to any other generator. Generator points can represent anything with a location. For example, they might be automated teller machines (ATMs) in a city. A Voronoi diagram can help predict patronage by determining which (nearest) ATM customers will use.

In another example, generators could map locations to avoid, such as toxic waste sites. In this case, the boundaries of the Voronoi regions would represent the maximum distance from any site, thereby helping mapmakers determine the safest route.

Reitsma took the Voronoi diagram a step further. He was interested in how to make each cell in the diagram proportional to its importance. For instance, a Web site on the financial crisis that is twice as popular or large as another site should take up twice as much space.

Proportioning a cell’s area takes more than a simple equation. Reitsma and his research assistant, Stanislav Trubin, who is a computer scientist now working at Amazon.com, invented the Adaptive Voronoi Diagram. This adapted diagramming process uses an algorithm that iteratively weighs the distance from points in the regions to their generators until the best solution is found.

To explain how it works, Reitsma turns to microbiology. Let’s say three points on a piece of paper represent three bacterial colonies that grow concentrically, but at different rates. “Assuming the colonies will not penetrate each other, if each one grows at a different rate, the boundaries between the colonies become curved,” said Reitsma. Additionally, the colony that grows the fastest will take up the most real estate.

The adaptive Voronoi algorithm also can define a cell’s area in relationship to its popularity, or any other measure of relevance. The end result is an Adaptive Voronoi Diagram—a network of colorful, weighted cells with curved boundaries.

Adaptive Voronoi Diagrams have a number of potential applications in information management. Libraries could represent digital collections in visual form to help users see the entire set of online resources. Businesses could glean information on the purchasing behavior of different population segments. The popularity or importance of an item could be defined in any way the user wants, such as the number of hits on a Web site, the number of users within a social media site, or the quantity of e-journals in a library’s collection.

“This is important for business because businesses are information processing entities,” Reitsma said. “Maybe these maps can help us better understand what these virtual spaces look like, how we can navigate them, and what they really mean.”

Reitsma said his management information systems colleagues at the OSU College of Business have been tremendously supportive of his teaching and research efforts. “We have a small group, and I’ve been really impressed with how easy it is for us to work together,” Reitsma said.

Although his research is currently theoretical, Reitsma sees lots of potential for the Adaptive Voronoi Diagram. Don’t be surprised if you see a two-dimensional map of your search results when you visit Google in the future.