Centerpoint theorems for wedgesReportar como inadecuado

Centerpoint theorems for wedges - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Department. of Computer Science Illinois 2 UPC - Universitat Politècnica de Catalunya Barcelona 3 Computational Geometry Lab

Abstract : The Centerpoint Theorem states that, for any set S of n points in Rd, there exists a point p in Rd such that every closed halfspace containing p contains at least n-d + 1 points of S. We consider generalizations of the Centerpoint Theorem in which halfspaces are replaced with wedges cones of angle alpha. In R2, we give bounds that are tight for all values of ff and give an On time algorithm to find a point satisfying these bounds. We also give partial results for R3 and, more generally, Rd.

Autor: Jeff Erickson - Ferran Hurtado - Pat Morin -



Documentos relacionados