prof. dr. Marc van Kreveld

Raster and Vector Geometry for Nonogram Puzzle Generation

In this talk we'll take a look at various types of puzzle games and how to generate them, in particular a new type of nonogram puzzle. Generation involves converting a line drawing into a coarse pixel drawing, which we study in more detail.

We will consider Japanese picture puzzles, also known as nonograms. They consist of a grid that must be partly colored black and partly left white, which reveals a picture. We will consider how we can convert a line drawing onto a grid for nonogram puzzle generation. Due to the coarseness of the grid, this conversion is not precise, and we will see if we can bound it in the Hausdorff error metric. We will also show that nonogram puzzles exist without a grid, and examine how a line drawing can be converted into such a puzzle. During the presentation some more new puzzles of various types will be shown.

Speaker:

prof. dr. Marc van Kreveld

Professor of Computational Geometry and its Application at the Department of Information and Computing Sciences at Utrecht University.

Scientific director at the Department of Information and Computing Sciences at Utrecht University.

He obtained his PhD in 1992 and has written many papers over the years, mostly on geometric algorithms, geographic information systems, graph drawing and some other topics, including puzzle games.

dr. van Kreveld's favorite game genre for research is puzzle games. He used to program and play games a lot when he was young and had a Commodore 64 back in the 80s. He plays board games regularly.