Name
Abstract | ||
|---|---|---|
We are given a set S of points in the Euclidean plane. We assume that S is in general position. A simple polygon P is a surrounding polygon of S if each vertex of P is a point in S and every point in S is either inside P or a vertex of P. In this paper, we present an enumeration algorithm of the surrounding polygons for a given point set. Our algorithm is based on reverse search by Avis and Fukuda and enumerates all the surrounding polygons in polynomial delay and quadratic space. It also provides the first space efficient method to generate all simple polygonizations on a given point set in exponential time. By relating these two problems we provide an upper bound on the number of surrounding polygons. (C) 2020 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.dam.2020.03.034 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Polygons, Surrounding polygons, Simple polygonizations, Enumeration algorithms, Polynomial delay | Journal | 303 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Katsuhisa Yamanaka | 1 | 60 | 15.73 |
| David Avis | 2 | 0 | 0.34 |
| Takashi Horiyama | 3 | 81 | 19.76 |
| Yoshio Okamoto | 4 | 170 | 28.50 |
| Ryuhei Uehara | 5 | 528 | 75.38 |
| Tanami Yamauchi | 6 | 0 | 0.34 |