New answers tagged computational-geometry
3
Take a look at this paper. You can interpret each coordinate pair in your grid that is part of at least one input rectangle as being part of a polygon $P$, and every coordinate pair that does not belong to any input rectangles as not being part of $P$.
Then the problem becomes partitioning $P$ into the smallest number of non-overlapping rectangles. The ...
3
The answer is "No". Please see a counterexample below:
2
From what I understand, the problem the paper is trying to solve is a gap problem of deciding whether $X$ is $(k,b)$-clusterable, or at least $\epsilon$-far from being $(k,2b)$-clusterable. Since they explained why the algorithm always accepts when $X$ is $(k,b)$-clusterable, now they move on to explain what happens when $X$ is at least $\epsilon$-far from ...
1
There are no "wrong" representatives assuming that $X$ is $(k,b)$-clusterable.
Think of it like that: $X$ can be divided into $k$ clusters. Say you chose some arbitrary node $x\in X$ to be a representative (doesn't matter which point!). Then, denote for any cluster $C$ such that $x\in C$, we know that for any two points $a,b\in C_x$, $dist(a,c)\le ...
Top 50 recent answers are included
