The search functionality is under construction.

Author Search Result

[Author] Shunta TERUI(1hit)

1-1hit
  • Enumerating Empty and Surrounding Polygons

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

     
    PAPER-Algorithms and Data Structures

      Pubricized:
    2023/04/03
      Vol:
    E106-A No:9
      Page(s):
    1082-1091

    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.