I'm reading about Multiset Size Verification Problem and in the following paper - http://www.skynet.ie/~sos/mapviewer/docs/Voronoi_Diagram_Notes_2.pdf - I got stuck just on the first lemma. However, since my concrete problem is rather specific, I'll describe it as self-contained, so that no background in terms of what MSV really is will be needed (but I encourage you to check it :)).

Fix natural $k, n$ such that $k \le n$. Let $$ Y = \{ (z_1, z_2, \ldots, z_n) \in \mathbb{R}^n : |\{ z_1, z_2, \ldots, z_n \}| = k \} $$ Next, let $$ T = \{ (z_1, z_2, \ldots, z_n) \in \mathbb{R}^n : \{z_1, z_2, \ldots, z_k \} = \{1, 2, \ldots, k \} \ \text{and} \ z_i \in \{1, 2, \ldots, k \} \ for \ i \in \{ k+1, \ldots, n \} \} $$ In the paper that I linked to, they claim that for any distinct $a, b \in T$, on any continuous path from $a$ to $b$ we must encounter a point $p$ that is outside $Y$, i.e. $p \in \mathbb{R}^n - Y$. Apparently, it is not hard to see that, but I have a big difficulty proving it formally.

I wasn't sure whether to ask this question on Math community, or here, since the problem itself is purely mathematical. It's closely related to CS, though.


Consider any path from $a \in T$ to $b \in T$ inside $Y$. Let $t$ be the first time in which the first $k$ coordinates are not distinct. Prior to time $t$, for each $1 \leq i \leq k$, all coordinates in $j \in \{k+1,\ldots,n\}$ such that $a_j = a_i$ must keep satisfying this relation along the path, since otherwise there will be more than $k$ distinct values. Therefore at the point $t$, there will be fewer than $k$ distinct values. We conclude that the first $k$ coordinates always remain distinct, and that they determine the rest of the vector. In particular, the values in the first $k$ coordinates can't cross each other: if $a_i < b_i$ and $a_j > b_j$ then the intermediate value theorem shows that at some point $x$ along the path, $x_i = x_j$. We conclude that $a_1,\ldots,a_k = b_1,\ldots,b_k$. Since the first $k$ coordinates determine the rest, in fact $a = b$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.