IEICE TRANSACTIONS on Fundamentals
Enumerating Empty and Surrounding Polygons
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
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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(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.
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(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.},
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(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.
ER -
English
