Tiles

I am sharing one early project in my Ph.D. that I could not get published. I think it is kind of cute and it would be a shame if I’d just delete it. It’s a way to overlay spatial locations by non-overlapping grid cells which are aligned only on one axis. The other axis is free so as to better capture the point cloud’s outline. Reviewers sort of liked it but rejected our submissions because the produced partition does not have well-defined properties, such as optimal outline-tracking, minimum number of cells, lower bound on covered locations, etc. I came up with this algorithm after attending a computational geometry class, where similar 1D scanning algorithms are used to find, e.g., line intersections (“sweep line”). We evaluated the algorithm with quality metrics on real data and found that it led consistently to fewer cells¹, but interestingly the match to the point cloud’s outline can become worse than on a normal grid with smaller cells.

You can find the submitted paper here and an implementation in R here.