The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Kami diberi satu set S of n titik dalam satah Euclidean. Kami menganggap bahawa S berada dalam kedudukan umum. Poligon mudah P merupakan poligon kosong of S jika setiap bucu daripada P adalah titik masuk S dan setiap titik masuk S sama ada di luar P atau puncak daripada P. Dalam kertas ini, kami mempertimbangkan masalah menghitung semua poligon kosong bagi set titik tertentu. Untuk mereka bentuk algoritma penghitungan yang cekap, kami menggunakan carian terbalik oleh Avis dan Fukuda dengan senarai anak. Kami mencadangkan algoritma yang menyenaraikan semua poligon kosong bagi S in O(n2|ε(S)|)-masa, di mana ε(S) ialah set poligon kosong bagi S. Selain itu, dengan menggunakan idea yang sama kepada masalah menghitung poligon sekeliling set titik tertentu S, kami mencadangkan algoritma penghitungan yang menyenaraikannya O(n2)-delay, manakala algoritma yang diketahui menghitung dalam O(n2 log n)-kelewatan, di mana a poligon sekeliling of S ialah poligon supaya setiap bucu poligon ialah titik masuk S dan setiap titik masuk S sama ada di dalam poligon atau bucu poligon.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -