The search functionality is under construction.

The search functionality is under construction.

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*(*n*^{2}|*ε*(*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*(*n*^{2})-delay, while the known algorithm enumerates in *O*(*n*^{2} 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

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Shunta TERUI, Katsuhisa YAMANAKA, Takashi HIRAYAMA, Takashi HORIYAMA, Kazuhiro KURITA, Takeaki UNO, "Enumerating Empty and Surrounding Polygons" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 9, pp. 1082-1091, September 2023, doi: 10.1587/transfun.2022DMP0007.

Abstract: 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*(*n*^{2}|*ε*(*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*(*n*^{2})-delay, while the known algorithm enumerates in *O*(*n*^{2} 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022DMP0007/_p

Copy

@ARTICLE{e106-a_9_1082,

author={Shunta TERUI, Katsuhisa YAMANAKA, Takashi HIRAYAMA, Takashi HORIYAMA, Kazuhiro KURITA, Takeaki UNO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Enumerating Empty and Surrounding Polygons},

year={2023},

volume={E106-A},

number={9},

pages={1082-1091},

abstract={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*(*n*^{2}|*ε*(*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*(*n*^{2})-delay, while the known algorithm enumerates in *O*(*n*^{2} 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.},

keywords={},

doi={10.1587/transfun.2022DMP0007},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

TI - Enumerating Empty and Surrounding Polygons

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1082

EP - 1091

AU - Shunta TERUI

AU - Katsuhisa YAMANAKA

AU - Takashi HIRAYAMA

AU - Takashi HORIYAMA

AU - Kazuhiro KURITA

AU - Takeaki UNO

PY - 2023

DO - 10.1587/transfun.2022DMP0007

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E106-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2023

AB - 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*(*n*^{2}|*ε*(*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*(*n*^{2})-delay, while the known algorithm enumerates in *O*(*n*^{2} 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.

ER -