Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Shattering Configurations of Points With Hyperplanes.

Shattering Configurations of Points With Hyperplanes.

File(s)
91-1199.pdf (855.39 KB)
91-1199.ps (214.28 KB)
Permanent Link(s)
https://hdl.handle.net/1813/7039
Collections
Computer Science Technical Reports
Author
Freimer, Robert
Abstract

An arrangement of hyperplanes $\cal A$ in $\Re^d$ is said to shatter a point set $\cal O$ if each point of $\cal O$ is contained within the interior of its own cell of $\cal A$. In this paper, we investigate the number of hyperplanes required by an arrangement that shatters a set of $n$ points in general position. We show that such sets can require between $\Omega(\sqrt[d]{n})$ and $\Omega(n)$ shattering hyperplanes. We also provide an algorithm that finds a linear-size shattering for such sets. The number of hyperplanes produced exceeds the requirements of the worst known example in $\Re^d$ by at most constant, which depends only on $d$. We also give some results for when the points are in general convex position.

Date Issued
1991-04
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1199
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance