Introduction

What is Voronoi diagram?

Suppose that geometric objects are given in a space, a Voronoi diagram is defined by a set of Voronoi regions which are closer to the corresponding object than any other objects. Below figures show the Voronoi diagrams of point and circle sets in a plane. Once such a Voronoi diagram is represented in an efficient data structure, we can efficiently and exactly analyze various structural characteristics of particles in the space.

Figure 1: Voronoi diagram for points	Figure 2: Voronoi diagram for circles

Research objectives

Our research group study the exact and fast computation methodology to analyze spatial structure of system which consists of particles, and implement the software based on developed theory.

Based on these studies, our research target is solving important problems efficiently in various applied fields include life engineering and material engineering efficiently.

• Development of the theories and algorithms for Euclidean Voronoi diagram of spheres in 3D and higher dimensions
• Development of spatial reasoning algorithms to solve various application problems
• Identifying and solving important application problems from domains of biology, molecular chemistry, and material sciences

Potential value of the research

Since the Voronoi diagram is one of the most efficient and effective tool for analyzing spatial structure of particles, our understanding of atomic structure for nature including both organisms and materials will be significantly improved. In biology, for example, Voronoi diagrams will make very hard problems such as identifying pockets or understanding protein dockings, which is core problem in drug design, easier ones. In material science, it can help to understand spatial distribution of the particles consisting material and the spatial characteristics efficiently. Therefore, our research on Voronoi diagrams will enhance the quality of human life and will contribute the competitiveness of industry.