Speaker

Sang Won Bae

Title

Counting Polygons and Holes: Algorithms and Complexity

Abstract

Given a finite set S of points in the plane in general position, a polygon of k corners chosen from S is called a k-gon of S, and a k-gon is called a k-hole if it contains no other points of S in its interior. In this talk, we are interested in the very fundamental problem of counting k-gons or k-holes of S for a given set S and an integer k. Considering the computational complexity of these counting problems, this talk covers known combinatorial results on k-gons and k-holes, algorithms that count them, lower bounds, and open research problems from the theoretical point of view.

Bio

Sang Won Bae received a PhD in computer science at KAIST in 2008. His research interests include research problems in discrete and computational geometry and their applications. Currently, he works as a professor in Kyonggi University.

Language

Korean (Offline)