August 21, 2018

NCH: closing the gap

Introduction Following up with my last post on NCH being roto-translation invariant, the idea of this one is to cover what I consider the most important gaps left by the original brief paper. My expectation is that doing this will help understand better why NCH works, and hopefully gain some insight into how to improve it. Equivalence of formulations Equation (4) in the paper says: $$f_i^{r_i} (x) = \frac{1}{2 r_i} (r_i^2 - || x - (p_i + r_i n_i) ||^2)$$ Read more

August 20, 2018

NCH is roto-translation invariant

Introduction I have recently started my thesis on 3D surface reconstruction. One way to do so is to define a surface as the zero level set of a function $f : \mathbb{R}^3 \to \mathbb{R}$, and then find some way to build this function out of a set of points $\mathcal{P} \subset \mathbb{R}^3$. NCH is a method that allows you to define such a function starting from a point cloud along with their normals, which tell you which way is the inside of the surface. Read more

June 2, 2018

Processing Trees with Recursion Schemes

A long time ago, I was in touch with a production system whose purpose was to run a piece of data through a decision tree. At every step, the output could be Good, Bad, Move Left, or Move Right; there were no leaves, since at the end you were supposed to always have returned either Good or Bad (this means it would be an error for you to get there). Read more

May 2, 2018

Understanding Modulo Bias

It is often said that this code: unsigned int randomNumber = rand() % k; is a bad idea, at least if you are expecting a uniform distribution. I'm going to try and explore this topic in a more formal fashion than I have seen so far. The reason why it is bad is pretty elementary and easy to understand: imagine you have a random generator that outputs values between \(0\) and \(9\) (i. Read more

April 30, 2016

Yet Another Proof of Brooke's Theorem

A classical result from Graph theory is that given \(G\) an undirected graph: \chi(G) \leq \Delta(G) + 1 Where \(\chi(G)\) is the minimum number of colors required to paint the nodes of \(G\) with the usual restriction that no node has the same color as any of its neighbors, and \(\Delta(G) = max_{v \in V(G)}(dg(v))\), that is, the maximum degree. This result is known as Brooke's Theorem. The usual way to prove this result is to use the Greedy coloring algorithm: go through every node, and pick the lowest color not yet used by any of its neighbors. Read more