Interesting Esoterica

Programming the Hilbert curve

Article by John Skilling
  • Published in 2004
  • Added on
The Hilbert curve has previously been constructed recursively, using \(p\) levels of recursion of \(n\)‐bit Gray codes to attain a precision of \(p\) bits in \(n\) dimensions. Implementations have reflected the awkwardness of aligning the recursive steps to preserve geometrical adjacency. We point out that a single global Gray code can instead be applied to all \(np\) bits of a Hilbert length. Although this “over‐transforms” the length, the excess work can be undone in a single pass over the bits, leading to compact and efficient computer code.

Links

Other information

key
ProgrammingtheHilbertcurve
type
article
date_added
2021-02-12
date_published
2004-06-10

BibTeX entry

@article{ProgrammingtheHilbertcurve,
	key = {ProgrammingtheHilbertcurve},
	type = {article},
	title = {Programming the Hilbert curve},
	author = {John Skilling},
	abstract = {The Hilbert curve has previously been constructed recursively, using \(p\) levels of recursion of \(n\)‐bit Gray codes to attain a precision of \(p\) bits in \(n\) dimensions. Implementations have reflected the awkwardness of aligning the recursive steps to preserve geometrical adjacency. We point out that a single global Gray code can instead be applied to all \(np\) bits of a Hilbert length. Although this “over‐transforms” the length, the excess work can be undone in a single pass over the bits, leading to compact and efficient computer code.},
	comment = {},
	date_added = {2021-02-12},
	date_published = {2004-06-10},
	urls = {https://aip.scitation.org/doi/abs/10.1063/1.1751381},
	collections = {basically-computer-science,things-to-make-and-do},
	url = {https://aip.scitation.org/doi/abs/10.1063/1.1751381},
	year = 2004,
	urldate = {2021-02-12}
}