<p>If the distance function originates from the Euclidean norm (<span class="math-container">$l_2$</span>-norm), then the Voronoi diagram of <span class="math-container">$n$</span> points in a compact subset of <span class="math-container">$\mathbb{R}^d$</span> consists of cells that are convex polytopes. In this case, the maximum number of faces from a cell is <span class="math-container">$n(n-1)/2$</span>.</p>
<p>How many faces does a cell have when the distance changes from the <span class="math-container">$l_2$</span> to the <span class="math-container">$l_1$</span>-norm? I know already  that the Voronoi cells in this case are not convex sets. What can I do if I want a bound for the VC dimension of a Voronoi diagram under the <span class="math-container">$l_1$</span>-norm ?</p>

CC BY-SA 4.0
2020-09-10T18:33:16.400Z
Can you give a specific example of where the $\ell_1$ distance yields non-convex Voronoi cells?
Aryeh
CC BY-SA 4.0
2020-09-11T19:27:15.683Z
Correct me if I am wrong: Take $A = [-2, 2] \times [-2, 2] \subset \mathbb{R}^2$ as the compact set and two points, $p_1 = (1,1)$, $p_2 = (1,0)$. The bisector  $\{x: ||x-p_1||_\infty = ||x-p_2||_\infty \}$  is piece-wise linear curve.
AlexGj
CC BY-SA 4.0
2020-09-11T19:52:42.743Z
@user2798850 Did you want the $\ell_1$ norm, or the $\ell_\infty$ norm though? For the $\ell_\infty$ norm "Voronoi Polytopes for Polyhedra norms on Lattices" has [this example](https://ars.els-cdn.com/content/image/1-s2.0-S0166218X14003990-gr1.jpg). Here $V_< = \{x\in \mathbb{R}^n \mid N(x - v) < N(x - w) \text{ for }v\in\mathbb{Z}^n\setminus \{v\}\}$, and $V_\leq$ is the same definition with $<$ replaced with $\leq$. Importantly $V_\leq$ is not the closure of $V_<$, as one would expect from the $\ell_2$ norm case.
Mark Schultz-Wu
CC BY-SA 4.0
2020-09-11T21:02:11.750Z
@Mark thank you for the reference. I am  interested in the $\mathcal{l}_1$-norm.
AlexGj
CC BY-SA 4.0
2020-09-13T13:24:10.657Z
@AlexGj doesn't your example use $\ell_\infty$ rather than $\ell_1$?
Aryeh
CC BY-SA 4.0
2020-09-13T16:30:38.933Z
In any case, for $\ell_2$ distance, the problem was analyzed here: https://papers.nips.cc/paper/2261-margin-analysis-of-the-lvq-algorithm.pdf
Aryeh
CC BY-SA 4.0
2020-09-13T16:30:52.970Z
Analyzing the general $\ell_p$ case would be interesting.
Aryeh
CC BY-SA 4.0
2020-09-14T12:22:41.813Z
@Aryeh Thank you for the reference (nips paper).
AlexGj
CC BY-SA 4.0
2020-09-14T12:51:43.990Z
@AlexGj I conjecture that a similar bound (in terms of dimension, not margin) holds for other $\ell_p$ norms, and I have a proof strategy in mind. Convince me that it's sufficiently important/interesting and I'll try to work it out :)
Aryeh
CC BY-SA 4.0
2020-09-16T07:46:02.687Z
@Aryeh There is a theorem about data-dependent partitioning classifiers [Theorem 21.2, "A probabilistic theory of pattern recognition", Devroye et al.] which states that, if a partition (of the observation space) has finite VC dimension (plus some requirements on the diameter of sets), then the classifier is consistent. And I was wondering what happens if we use k-means with different metrics to produce such partitions.
AlexGj
CC BY-SA 4.0
2020-09-16T07:46:45.270Z
@Aryeh Using  modern aproximate nearest-neighbor search libraries (like FAISS) such partitioning classifiers are easy to implement in large scale data problems. I don't know if I am able to confince you about the utility of my question, but  I find it a good excercise to sharpen my skills.  I would greatly appreciate it if you kindly give me some hints.
AlexGj
CC BY-SA 4.0
2020-09-16T09:04:32.013Z
My idea is to go through their proof (again, not the margin part -- just the Euclidean dimension aspect) and verify that it holds for other $\ell_p$ norms, possibly with different constants. This requires some technical knowledge, though. Why don't you send me an email, you can get it from my homepage https://www.cs.bgu.ac.il/~karyeh/
Aryeh
CC BY-SA 4.0
2020-09-17T16:06:48.897Z
@Aryeh I will write to you soon. Thanks again!
AlexGj
<combinatorics><vc-dimension>
VC dimension of Voronoi cells (Manhattan distance)
AlexGj
# VC dimension of Voronoi cells (Manhattan distance)

(Asked by: username_0 on 2020-09-10)

If the distance function originates from the Euclidean norm ($l\_2$-norm), then the Voronoi diagram of $n$ points in a compact subset of $\mathbb{R}^d$ consists of cells that are convex polytopes. In this case, the maximum number of faces from a cell is $n(n-1)/2$.

How many faces does a cell have when the distance changes from the $l\_2$ to the $l\_1$-norm? I know already that the Voronoi cells in this case are not convex sets. What can I do if I want a bound for the VC dimension of a Voronoi diagram under the $l\_1$-norm ?

**Tags:** combinatorics, vc-dimension

> **Comments:**
> **username_1**: Can you give a specific example of where the $\ell_1$ distance yields non-convex Voronoi cells?  
> **username_0**: Correct me if I am wrong: Take $A = [-2, 2] \times [-2, 2] \subset \mathbb{R}^2$ as the compact set and two points, $p_1 = (1,1)$, $p_2 = (1,0)$. The bisector  $\{x: ||x-p_1||_\infty = ||x-p_2||_\infty \}$  is piece-wise linear curve.  
> **username_2**: @user2798850 Did you want the $\ell_1$ norm, or the $\ell_\infty$ norm though? For the $\ell_\infty$ norm "Voronoi Polytopes for Polyhedra norms on Lattices" has [this example](https://ars.els-cdn.com/content/image/1-s2.0-S0166218X14003990-gr1.jpg). Here $V_< = \{x\in \mathbb{R}^n \mid N(x - v) < N(x - w) \text{ for }v\in\mathbb{Z}^n\setminus \{v\}\}$, and $V_\leq$ is the same definition with $<$ replaced with $\leq$. Importantly $V_\leq$ is not the closure of $V_<$, as one would expect from the $\ell_2$ norm case.  
> **username_0**: @Mark thank you for the reference. I am  interested in the $\mathcal{l}_1$-norm.  
> **username_1**: @username_0 doesn't your example use $\ell_\infty$ rather than $\ell_1$?  
> **username_1**: In any case, for $\ell_2$ distance, the problem was analyzed here: https://papers.nips.cc/paper/2261-margin-analysis-of-the-lvq-algorithm.pdf  
> **username_1**: Analyzing the general $\ell_p$ case would be interesting.  
> **username_0**: @username_1 Thank you for the reference (nips paper).  
> **username_1**: @username_0 I conjecture that a similar bound (in terms of dimension, not margin) holds for other $\ell_p$ norms, and I have a proof strategy in mind. Convince me that it's sufficiently important/interesting and I'll try to work it out :)  
> **username_0**: @username_1 There is a theorem about data-dependent partitioning classifiers [Theorem 21.2, "A probabilistic theory of pattern recognition", Devroye et al.] which states that, if a partition (of the observation space) has finite VC dimension (plus some requirements on the diameter of sets), then the classifier is consistent. And I was wondering what happens if we use k-means with different metrics to produce such partitions.  
> **username_0**: @username_1 Using  modern aproximate nearest-neighbor search libraries (like FAISS) such partitioning classifiers are easy to implement in large scale data problems. I don't know if I am able to confince you about the utility of my question, but  I find it a good excercise to sharpen my skills.  I would greatly appreciate it if you kindly give me some hints.  
> **username_1**: My idea is to go through their proof (again, not the margin part -- just the Euclidean dimension aspect) and verify that it holds for other $\ell_p$ norms, possibly with different constants. This requires some technical knowledge, though. Why don't you send me an email, you can get it from my homepage https://www.cs.bgu.ac.il/~karyeh/  
> **username_0**: @username_1 I will write to you soon. Thanks again!  

---

## 0 answers

