On the metric properties of discrete space-filling curves
1Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa.
Abstract:
A space-filling curve is a linear traversal of a discrete finite multidimensional space. In order for this traversal to be useful in many applications, the curve should preserve "locality". We quantify "locality" and bound the locality of multidimensional space-filling curves. Classic Hilbert space-filling curves come close to achieving optimal locality.
Related Concept Videos
Space Curves
A space curve describes the path followed by a particle moving through three-dimensional space. Unlike plane curves, which are confined to two coordinates, space curves require three coordinate functions. If t is a parameter, the position of the particle is represented by the vector function\begin{equation*}\mathbf{r}(t)=\langle x(t),y(t),z(t)\rangle,\end{equation*}where x(t), y(t), and z(t) are differentiable functions of t. As t varies over an interval, the endpoints of the position vectors...
Curvature and Its Interpretation
Curvature describes how rapidly a curve changes direction at a particular point. A curve with a small curvature bends gently, while a curve with a large curvature turns sharply. For a space curve, the position of a moving object can be described by a vector-valued function r(t), where t often represents time. The direction of motion is determined by the tangent vector, and the unit tangent vector is obtained by normalizing the derivative of the position vector.The unit tangent vector gives the...
Properties of Continuous Functions
Continuous functions exhibit smooth, uninterrupted behavior, and combining them through standard operations retains this continuity. If f and g are continuous at a point a, then the functions f+g, f-g, cf (where c is a constant), fg, and fg (provided g(a)a) are also continuous at a. This allows the construction of complex functions from simpler continuous parts without losing smoothness.Polynomials, which are expressions formed by sums of powers of x with constant coefficients, are continuous...
Parametric Surfaces
A parametric surface in three-dimensional space is defined through a vector-valued function\begin{equation*}\mathbf{r}(u, v) = x(u, v)\mathbf{i} + y(u, v)\mathbf{j} + z(u, v)\mathbf{k}\end{equation*}where u and v are parameters within a specified domain D in the uv-plane. The functions x(u, v), y(u, v), and z(u, v) define the coordinates of points on the surface. As u and v vary over D, the position vector r(u, v) traces a continuous surface in space. This parametric representation is essential...
Degree of Curvature and Radius of Curvature
The degree of curvature and the radius of curvature are fundamental concepts in determining the sharpness or smoothness of a curve. The degree of curvature is a measure of how steeply a curve bends and can be determined using the chord basis or the arc basis. In the chord basis method, the degree of curvature is defined as the central angle subtended by a chord of 30.48 meters, helping in the calculation of the radius of the curve. The arc basis method defines the degree of curvature as the...
Torsion in Vector Calculus
A toy train ascending a winding track that curves and tilts offers an intuitive view of torsion, a key geometric concept in the study of space curves. While curvature measures how sharply a path bends, torsion captures how the path twists out of the plane of bending. This twisting behavior is crucial in understanding three-dimensional motion and is precisely described using the Frenet–Serret framework.At each point along a space curve, the Frenet–Serret frame consists of three orthogonal unit...


