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 cells1, but interestingly the match to the point cloud’s outline can become worse than on a normal grid with smaller cells.
![Locations in Europe covered by normal grid.](/media/tiles/grid.png)
Locations in Europe covered by normal grid.
![Locations in Europe covered by grid with one free axis.](/media/tiles/tiles.png)
Locations in Europe covered by grid with one free axis.
You can find the submitted paper here and an implementation in R here.
-
This entails on average more data points per cell, which in turn should lead to more reliable summary statistics, should they be computed per cell. ↩︎