Space-filling curves, constructively
Andrej Bauer discusses space-filling curves, focusing on the Hilbert curve's surjectivity and its constructive properties. He introduces generalized curves to ensure coverage and explores limitations in constructive mathematics.
Read original article
In a recent blog post, Andrej Bauer discusses the concept of space-filling curves, particularly focusing on the Hilbert curve and its constructive properties. He references the original discoveries by Giuseppe Peano and David Hilbert in the late 19th century, noting that while the curves are defined constructively, their surjectivity requires further examination. Bauer presents Theorem 1, which establishes that the Hilbert curve is surjective in a classical sense, as it approaches every point in the unit square. However, he points out that constructively, the curve's self-similar nature complicates this, necessitating a modification to ensure coverage of the square.
To address this, he introduces a generalized Hilbert curve defined with a scaling factor, α, which allows for overlapping segments that ensure surjectivity for values between 0.5 and 1, as stated in Theorem 2. Theorem 3 explores the limitations of constructing a square-filling curve in the topos of sheaves, concluding that such a curve cannot exist due to the requirement for local sections, which may not be feasible.
Bauer emphasizes the distinction between classical and constructive mathematics, illustrating the complexities involved in defining and proving properties of space-filling curves. He also notes that comments on the blog are currently disabled but invites readers to engage with him on Mastodon or directly.
Related
Desperately Seeking Squircles
An engineer aims to incorporate Apple's 'squircle' shape into Figma, navigating mathematical complexities with superellipse formulas and Bézier curves. Challenges in mirroring and transitioning the shape prompt a proposed smoothing scheme for versatile designs. Differential geometry aids in mathematically analyzing the squircle's perimeter, showcasing the intricate process of digital design translation.
A mathematical thought experiment for accepting the continuum hypothesis
The article explores the theoretical implications of considering the continuum hypothesis a fundamental axiom in mathematics, potentially impacting mathematical reasoning and structures. Alternative foundational schemes and implications of historical developments are discussed.
The "Horgan Surface" and "The Death of Proof"
John Horgan's namesake "Horgan surface" in mathematics sparked debate on proofs and technology's role. Despite controversy, he reflects on evolving math and the impact of computerization on human discovery.
Undergraduate Texts in Mathematical Comics – A Tour of Complex Analysis
The website showcases mathematical comics by Andrea Tomatis, introducing rigorous concepts like Complex Analysis. Supported by the National Science Foundation, it combines math rigor with comics to engage readers effectively.
Closed form arc length parametrization is impossible for quadratic Bézier curves
The blog explores arc length parametrizations of Bézier curves, focusing on quadratic and cubic types in computer graphics. It discusses challenges, closed form solutions, Schanuel's conjecture, and limitations in mathematical contexts.
- Space-filling curves are recognized for their applications in database indexing, with several databases like DuckDB, SQL Server, and Postgres implementing Hilbert indexing for performance gains.
- Geohashing is highlighted as an interesting application of space-filling curves for location representation and indexing.
- Some commenters express skepticism about the practical effectiveness of space-filling curves, suggesting that simpler methods like Z-order indexing are more commonly used.
- Concerns are raised about the limitations of inverse mapping in Hilbert curves, which may not preserve locality as expected.
- There is interest in the artistic potential of space-filling curves, with inquiries about generative art applications.
11 commentsThere's a unique side-effect to Geohashes in that the value (`u4pruydqqvj`) can have it's end "lopped off" (i.e. cut down to `u4pru`) and it still represents a less precise, but generally accurate representation of the original lon/lat in most cases (when the curve isn't near the edge of the 2d map!). This allows you to index locations (lat/lon) using a string ('u4pru') which opens you up to doing b-tree, range queries, etc. in traditional database, with one field.
Just a rad math quirk! I'm not an expert, and it's a very dense book, but if someone really wants to get into this kind of stuff the "Bible" is "Foundations of Multidimensional and Metric Data Structures" by Hanan Samet.
DuckDB has a Hilbert index.
https://github.com/rustyconover/duckdb-lindel-extension
It’s not just DuckDB. SQL server and Postgres support Hilbert too.
The big idea is that you can project tuples e.g (lat, long) or just about any other tuple structure (string or floats) in a single integer, ordered in a way that is locality preserving.
Because most queries tend to lookup data close to each other, this can lead to performance gains. Parquet statistics can be built to be locality sensitive (locality defined broadly, not just numbers).
If you index on Hilbert, you can specific compute a max min of the Hilbert range of your predicate and eliminate looking outside that range, speeding up query performance.
All the stuff about database indexing and cache locality seems to have become obsolete with improvements in compilers; the overhead of computing the Hilbert curve indices is just too high. The indexing method that people seem to actually use is the Z-order/Morton order, which just interleaves bits and is mathematically less interesting [1].
Hilbert maps (x,y) -> h such that nearby h correspond to nearby x,y.
But the inverse isn’t true: similar x,y don’t always have similar h.
This is a problem for some applications where we are trying to find dense hot spots cheaply by only looking at h’s, but turns out this doesn’t work out so well.
With some of the recent work done with ClickHouse this has been an area I've had to learn about and, tbh, wish I had found this earlier.
Our CTO started using Morton curves for interesting purposes several months ago with initially piqued my interest and started me down the path.
https://reversedns.space/ (a map of the Internet) - Morton curve is used as a visualization tool;
https://adsb.exposed/ (a visualizer of air traffic) - Morton curve is used as a database index;
Our most recent release post dove into the usage of Hilbert curves in context of maintaining spatial locality for weather measurements
https://clickhouse.com/blog/clickhouse-release-24-06#hilbert...
Quite an interesting area of study and optimisation!
Related
Desperately Seeking Squircles
An engineer aims to incorporate Apple's 'squircle' shape into Figma, navigating mathematical complexities with superellipse formulas and Bézier curves. Challenges in mirroring and transitioning the shape prompt a proposed smoothing scheme for versatile designs. Differential geometry aids in mathematically analyzing the squircle's perimeter, showcasing the intricate process of digital design translation.
A mathematical thought experiment for accepting the continuum hypothesis
The article explores the theoretical implications of considering the continuum hypothesis a fundamental axiom in mathematics, potentially impacting mathematical reasoning and structures. Alternative foundational schemes and implications of historical developments are discussed.
The "Horgan Surface" and "The Death of Proof"
John Horgan's namesake "Horgan surface" in mathematics sparked debate on proofs and technology's role. Despite controversy, he reflects on evolving math and the impact of computerization on human discovery.
Undergraduate Texts in Mathematical Comics – A Tour of Complex Analysis
The website showcases mathematical comics by Andrea Tomatis, introducing rigorous concepts like Complex Analysis. Supported by the National Science Foundation, it combines math rigor with comics to engage readers effectively.
Closed form arc length parametrization is impossible for quadratic Bézier curves
The blog explores arc length parametrizations of Bézier curves, focusing on quadratic and cubic types in computer graphics. It discusses challenges, closed form solutions, Schanuel's conjecture, and limitations in mathematical contexts.