A Non-linear Lower Bound for Planar Epsilon-nets |
| |
| Authors: | Noga Alon |
| |
| Institution: | 1. Schools of Mathematics and Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 69978, Israel
2. Institute for Advanced Study, Princeton, NJ, 08540, USA
|
| |
| Abstract: | We show that the minimum possible size of an ε-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in
\frac1e\frac{1}{\epsilon}. This settles a problem raised by Matoušek, Seidel and Welzl (Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16–22, 1990). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
