The order of points on the second convex hull of a simple polygon
type: Item
instance of: scholarly article
title: The order of points on the second convex hull of a simple polygon
zbMATH Open document ID: 0829.05001
DOI: 10.1007/BF02570702
published in: Discrete \& Computational Geometry
publication date: 1996-01-10T00:00:00Z
full work available at URL: https://eudml.org/doc/131398
review text: Let \(V\) be a simple polygon on the plane, \(P\) be the convex hull of \(V\) and \(V_P\) be \(V \cap \partial P\). The convex hull \(Q\) of \(V- V_P\) is the second convex hull of \(V\), and \(V_Q = \{q_1, \dots, q_n\}\) is the set \(V \cap \partial Q\), where the vertices are numbered clockwise with respect to \(\partial Q\). The order in which the points \(\{q_1, \dots, q_n\}\) must be visited in any simple \(V\)-gon is characterized. Moreover, the number of possible orders is obtained. A permutation \(\pi_n\) of \(\{1, \dots, n\}\) is feasible if there is a set of points \(V\), with \(n\) vertices in \(\partial Q\) and one simple \(V\)-gon, that visits the vertices in \(V_Q\) only in the order given for the permutation. Theorem 6: A permutation of \(\{1,\dots, n\}\) is feasible if and only if it does not contain either the five-point or the six-point stars. The number of feasible permutations of \(n + 2\) points is \[ h_n = {125 \sqrt {5} \over 54 \sqrt {\pi}} n^{-3/2} 5^n + o(5^n n^{- 3/2}). \]
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 51L15
Mathematics Subject Classification ID: 05B25
zbMATH DE Number: 784601
zbMATH Keywords: order of points
zbMATH Keywords: simple polygon
zbMATH Keywords: convex hull
zbMATH Keywords: feasible permutations
author: Alfredo García
author: Javier Tejel
reviewed by: Alexandre A. Makhnev
MaRDI profile type: Publication
cites work: Q3939231
cites work: Q4057549
cites work: Q5187226
cites work: Q3216652
OpenAlex ID: W1980116975
description: scientific article; zbMATH DE number 784601