|
Descripción
|
|
|---|---|
|
We present three results related to the problem of giving lower bounds for the number of $(\leq k)$-facets of a set of points $S$: An oriented
simplex with vertices at points of $S$ is said to be a \emph{$j$-facet} of $S$ if it has exactly $j$ points in the positive side of its affine hull. Similarly, the simplex is said to be an \emph{$(\leq k)$-facet} if it has at most $k$ points in the positive side of its affine hull. We denote by $E_k(S)$ the number of $(\leq k)$-facets of $S$.
\begin{enumerate}
\item It was stated in \cite{ehss-89} and independently shown in \cite{af-lbrcn-05,LVWW} that if $S$ is a set of $n$ points in the plane in general position then $E_k(S)\geq \binom{k+2}{2}$.
Moreover, this bound was known to be tight for $k\leq \lfloor n/3 \rfloor -1$.
We study the structure of sets attaining this lower bound and show that if $E_k(S)=3\binom{k+2}{2}$ for a fixed $k\leq \lfloor n/3 \rfloor -1$, then its $\lceil\tfrac{k}{2}\rceil$ outermost layers are triangles and, moreover, $E_j(S)=3\binom{j+2}{2}$ for every $j | |
|
Internacional
|
Si |
|
Nombre congreso
|
International Conference on Computational Geometry and Graph Theory |
|
Tipo de participación
|
960 |
|
Lugar del congreso
|
Kyoto, Japón |
|
Revisores
|
Si |
|
ISBN o ISSN
|
-- |
|
DOI
|
|
|
Fecha inicio congreso
|
11/06/2007 |
|
Fecha fin congreso
|
15/06/2007 |
|
Desde la página
|
|
|
Hasta la página
|
|
|
Título de las actas
|
|