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
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.‎

Leave a Reply

Your email address will not be published. Required fields are marked *