Search of fractal space-filling curves with minimal dilation

DOI10.1007/S00454-022-00444-2arXiv2103.07344OpenAlexW4311255392MaRDI QIDQ6156091FDOQ6156091

Authors: Yuri V. Malykhin, E. V. Shchepin 

Publication date: 12 June 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We introduce an algorithm for a search of extremal fractal curves in large curve classes. It heavily uses SAT-solvers~ -- heuristic algorithms that find models for CNF boolean formulas. Our algorithm was implemented and applied to the search of fractal surjective curves $gammacolon[0,1]o[0,1{]}^d$ with minimal dilation ${\displaystyle }$ sup_{t_1<t_2}frac{|gamma(t_2)-gamma(t_1)|^d}{t_2-t_1}. ${\displaystyle }$ We report new results of that search in the case of Euclidean norm. We have found a new curve that we call "YE", a self-similar (monofractal) plane curve of genus $5imes5$ with dilation $5frac4373=5.5890ldots$. In dimension $3$ we have found facet-gated bifractals (that we call "Spring") of genus $2imes2imes2$ with dilation $<17$. In dimension $4$ we obtained that there is a curve with dilation $<62$. Some lower bounds on the dilation for wider classes of cubically decomposable curves are proved.

Full work available at URL: https://arxiv.org/abs/2103.07344

zbMATH Keywords

space-filling curvesminimal dilation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• PySAT: a Python toolkit for prototyping with SAT oracles
• Title not available (Why is that?)
• Attainment of maximum cube-to-linear ratio for three-dimensional Peano curves
• Space-Filling Curves
• Title not available (Why is that?)
• On Hölder maps of cubes
• Minimal Peano curve
• Improving Glucose for incremental SAT solving with assumptions: application to MUS extraction
• The dilation factor of the Peano-Hilbert curve
• Locality and bounding-box quality of two-dimensional space-filling curves
• Towards optimal locality in mesh-indexings
• One-side Peano curves of fractal genus 9
• How many three-dimensional Hilbert curves are there?
• Lower bounds for the square-to-linear ratio for plane Peano curves
• Minimal self-similar Peano curve of genus \(5 \times 5\)
• \(L_\infty\)-locality of three-dimensional Peano curves

This page was built for publication: Search of fractal space-filling curves with minimal dilation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6156091)