New results on lower bounds for the number of k-facets

Aichholzer, Oswin and Garcia Lopez de Lacalle, Jesus and Orden Martín, David and Ramos Alonso, Pedro A. (2008). New results on lower bounds for the number of k-facets. "Electronic Notes In Discrete Mathematics", v. 29 ; pp. 189-193. ISSN 1571-0653. https://doi.org/10.1016/j.endm.2007.07.033.

Description

Title: New results on lower bounds for the number of k-facets
Author/s:
  • Aichholzer, Oswin
  • Garcia Lopez de Lacalle, Jesus
  • Orden Martín, David
  • Ramos Alonso, Pedro A.
Item Type: Article
Título de Revista/Publicación: Electronic Notes In Discrete Mathematics
Date: August 2008
Volume: 29
Subjects:
Freetext Keywords: (≤ k)-edges, (≤ k)-facets
Faculty: E.U. de Informática (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (299kB) | Preview

Abstract

In this paper we present three different results dealing with the number of (≤ k)- facets of a set of points: (i) We give structural properties of sets in the plane that achieve the optimal lower bound 3_k+2 2 _ of (≤ k)-edges for a fixed k ≤ [n/3 ]− 1; (ii) We show that the new lower bound 3((k+2) 2 ) + 3((k−(n/ 3)+2) 2 ) for the number of (≤ k)-edges of a planar point set is optimal in the range [n/3] ≤ k ≤ [5n/12] − 1; (iii) We show that for k < n/4 the number of (≤ k)-facets of a set of n points in R3 in general position is at least 4((k+3 )3 ), and that this bound is tight in that range.

More information

Item ID: 2969
DC Identifier: http://oa.upm.es/2969/
OAI Identifier: oai:oa.upm.es:2969
DOI: 10.1016/j.endm.2007.07.033
Official URL: http://www.elsevier.com/wps/find/journaldescription.cws_home/681020/description#description
Deposited by: Memoria Investigacion
Deposited on: 30 Apr 2010 09:31
Last Modified: 20 Apr 2016 12:34
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM