In collaboration with

• Hong Kong University of Science and Technology.

This project is concerned with the recognition of Chinese characters and similar pattern matching problems. The same character can appear in a variety of shapes that differ geometrically. What remains invariant, however, is the ``combinatorial'' structure of the pattern: a number of strokes that intersect or touch each other in a prescribed way. A stroke may move relative to another stroke, but it will not suddenly appear on the other side of that stroke; this motivates the idea to consider patterns as drawings of planar graphs. Two graph drawings can be considered similar, if both the underlying graph and the geometry of the planar embedding are similar. The goal of this project is to lay the foundations for subsequent research by theoretically and experimentally developing a suitable measure of similarity, combining ideas from graph theory with the purely geometric definition of pattern matching used in computational geometry so far.