The search functionality is under construction.
The search functionality is under construction.

Enumerating Empty and Surrounding Polygons

Shunta TERUI, Katsuhisa YAMANAKA, Takashi HIRAYAMA, Takashi HORIYAMA, Kazuhiro KURITA, Takeaki UNO

  • Full Text Views

    1

  • Cite this

Summary :

We are given a set S of n points in the Euclidean plane. We assume that S is in general position. A simple polygon P is an empty polygon of S if each vertex of P is a point in S and every point in S is either outside P or a vertex of P. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of S in O(n2|ε(S)|)-time, where ε(S) is the set of empty polygons of S. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set S, we propose an enumeration algorithm that enumerates them in O(n2)-delay, while the known algorithm enumerates in O(n2 log n)-delay, where a surroundingpolygon of S is a polygon such that each vertex of the polygon is a point in S and every point in S is either inside the polygon or a vertex of the polygon.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1082-1091
Publication Date
2023/09/01
Publicized
2023/04/03
Online ISSN
1745-1337
DOI
10.1587/transfun.2022DMP0007
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category
Algorithms and Data Structures

Authors

Shunta TERUI
  Iwate University
Katsuhisa YAMANAKA
  Iwate University
Takashi HIRAYAMA
  Iwate University
Takashi HORIYAMA
  Hokkaido University
Kazuhiro KURITA
  Nagoya University
Takeaki UNO
  National Institute of Informatics

Keyword