Ε-net (computational geometry): Difference between revisions

Revision as of 04:39, 7 October 2018

Revision as of 15:16, 13 April 2020

Line 17:

| title = ε-nets and simplex range queries

| volume = 2

| year = 1987| doi-access = free

| year = 1987}}.</ref> In other words, any range that intersects at least a proportion ε of the elements of ''P'' must also intersect the ''ε''-net&nbsp;''N''.

For example, suppose ''X'' is the set of points in the two-dimensional plane, ''R'' is the set of closed filled rectangles (products of closed intervals), and ''P'' is the unit square [0,&nbsp;1]&nbsp;×&nbsp;[0,&nbsp;1]. Then the set N consisting of the 8 points shown in the adjacent diagram is a 1/4-net of P, because any closed filled rectangle intersecting at least 1/4 of the unit square must intersect one of these points. In fact, any (axis-parallel) square, regardless of size, will have a similar 8-point 1/4-net.

Line 40 ⟶ 41:

| url = http://www.ics.uci.edu/~goodrich/pubs/setcover.ps

| volume = 14

| year = 1995}}.</ref>| doi-access = free

}}.</ref>

== Probability theory ==