Enumerating Empty and Surrounding Polygons
-
- TERUI Shunta
- Iwate University
-
- YAMANAKA Katsuhisa
- Iwate University
-
- HIRAYAMA Takashi
- Iwate University
-
- HORIYAMA Takashi
- Hokkaido University
-
- KURITA Kazuhiro
- Nagoya University
-
- UNO Takeaki
- National Institute of Informatics
Abstract
<p>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.</p>
Journal
-
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E106.A (9), 1082-1091, 2023-09-01
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1390860255282467968
-
- ISSN
- 17451337
- 09168508
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
-
- Abstract License Flag
- Disallowed