# Quasi Metric for Generalization of Epsilon net

By | September 18, 2020

Here we mention the definition of $\epsilon$-net that came in the paper “Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets” by Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta & Marc Glisse ;

Assum $\chi$ is a set of $n$ points in a metric space $\mathcal{M}$.

$\epsilon$-packing: $\chi$ is an $\epsilon$-packing if any pair of points in $\chi$ are at least distance $\epsilon$ apart.

$\epsilon$-cover: $\chi$ is an $\epsilon$-cover if each point in $\mathcal{R}$ is at distance at most $\epsilon$ form some point of $\chi$.

$\epsilon$-net: $\chi$ is an $\epsilon$-net if it is an $\epsilon$-cover and $\epsilon$-packing simultaneously.

## $\epsilon_1, \epsilon_2$-net

For definition of quasi-metric ‎space‎‎‎ see the chapter 6 of the book “Non-Hausdorff Topology and Domain Theory ” by Jean Goubault-Larrecq.

Assume $(\mathcal{M}, d^*)$ be a‎ quasi-metric ‎space‎‎‎. ‎(‎ $d^*$ is not necessarily symmetric‎)‎.

$\epsilon_1,\epsilon_2$-packing‎: ( $‎\epsilon‎_1 \le ‎\epsilon‎_2$ ‎) A set $\chi$ of $n$ points in ‎ $‎\mathcal{M}‎$ ‎is ‎an‎ $\epsilon_1,\epsilon_2$-packing if

$‎min\{d^{*}(x_i,x_j), d^{*}(x_j,x_i)\} ‎\ge ‎‎\epsilon‎_1$

‎ ‎and

$‎max‎\{d^{*}(x_i,x_j), d^{*}(x_j,x_i)\} \ge \epsilon_2$

$\epsilon_1,\epsilon_2$-cover‎‎: ( $‎\epsilon‎_1 \le ‎\epsilon‎_2$ ‎) A set $\chi$ of $n$ points in ‎ $‎\mathcal{M}‎$ ‎is ‎an‎ $\epsilon_1,\epsilon_2$-cover if

‎‎$‎\forall ‎x_i \in \chi \ \ ‎\exists ‎x_j \in \chi \ ;‎‎$

$min \{d^{*}(x_i,x_j), d^{*}(x_j,x_i) \} \le \epsilon_1$
and
$max \{d^{*}(x_i,x_j), d^{*}(x_j,x_i) \} \le \epsilon_2$

$\epsilon_1,\epsilon_2$-net‎‎: ( $‎\epsilon‎_1 \le ‎\epsilon‎_2$ ‎) $\chi$ is an $\epsilon_1,\epsilon_2$-net‎‎ if it is an $\epsilon_1,\epsilon_2$-cover and $\epsilon_1,\epsilon_2$-packing simultaneously.

Question: Is $\epsilon_1,\epsilon_2$-net a generalization of $\epsilon$-net ?

Because of two following reasons, probably the answer is Yes:

1. ‎If‎ $(\mathcal{M}, d^*)$ be a metric space, then for all $x_i,x_j \in \chi$ ,‎ ‎ $d^{*}(x_i,x_j) = d^{*}(x_j,x_i)$. ‎Hence‎ $\epsilon_1,\epsilon_2$-net become ‎an $min\{‎\epsilon‎_1, \epsilon_2\} = \epsilon$-net.‎‎
2. ‎If‎ ‎ $\epsilon_1 = \epsilon_2 = ‎\epsilon‎$ ‎then‎ $\epsilon_1,\epsilon_2$-net is indeed an ‎ $‎\epsilon‎$-net.‎