JCSE, vol. 17, no. 3, pp.109-116, 2023

DOI: http://dx.doi.org/10.5626/JCSE.2023.17.3.109

On Counting Monotone Polygons and Holes in a Point Set

Sang Won Bae
Division of Artificial Intelligence and Computer Science, Kyonggi University, Suwon, Korea

Abstract: In this paper, we studied the problem of counting the number of monotone polygons in a given set S of n points in general position in the plane. A simple polygon is said to be monotone when any vertical line intersects its boundary at most twice. To our best knowledge, this counting problem remains unsolved and no nontrivial algorithm is known so far. As a research step forward to tackle the problem, we define a subclass of monotone polygons and present, for the first time, efficient algorithms that exactly count them.

Keyword: Erdos-zekeres problem; Counting problem; Monotone polygon; Discrete geometry; Computational geometry; Algorithm

Full Paper:   59 Downloads, 651 View