System Information Sciences

Design and Analysis of Information Systems B08

  • Prof. Takehiro Ito    
  • Assoc. Prof. Jinhee Chun    
  • Assis. Prof. Hiroshi Eto
Keywordsalgorithm theory, combinatorial reconfiguration, computational geometry

Building a Foundation of Algorithmic Techniques for High-Quality Information System Design

In highly reliable information systems, theory-based methods are playing important roles. In our laboratory, we are conducting research on mathematical modeling and algorithmic techniques, together with analysis of developed methods, that are useful for designing and analyzing information systems. With the diversification of information systems, our target research themes are diverse, and we are conducting research especially on "combinatorial reconfiguration" and "computational geometry" from the viewpoint of theoretical computer science.


(1) Combinatorial reconfiguration is a novel algorithmic concept that provides mathematical models and analysis for "transformations over state spaces." For example, when we need to change the current supply-configuration in a power distribution network, we wish to compute a switching procedure that does not cause a power failure even during the transformation. As another example, in sliding block puzzles like the 15-puzzle, we wish to compute a block-sliding procedure. They are typical examples of "transformations over state spaces" which are targets of combinatorial reconfiguration.


(2) Computational geometry is a field that introduces the concept of computational complexity into geometry and studies data structures and algorithm design. Our interests include a wide range of traditional computational geometry problems such as convex hull, set cover, Voronoi diagram, visibility, and shape matching. In addition, as applications of computational geometry, we are conducting research on image processing, image retrieval, GIS, digital line, data mining, etc. in order to solve various practical problems.

  • Image of power distribution system

  • Shape-based image retrieval system