We prove that there is, in every direction in Euclidean space, a line that misses every computably random point. We also prove that there exist, in every direction in Euclidean space, arbitrarily long line segments missing every double exponential time random point.
A.S.Besicovitch, Sur deux questions d’intégrabilité des fonctions, Journal de la Société de physique et de mathematique de l’Universite de Perm2 (1919), 105–123.
2.
A.S.Besicovitch, On Kakeya’s problem and a similar one, Mathematische Zeitschrift27 (1928), 312–320.
3.
A.S.Besicovitch, On the fundamental geometric properties of linearly measurable plane sets of points, Mathematische Annalen98 (1928), 422–464.
4.
A.S.Besicovitch, The Kakeya problem, American Mathematical Monthly70 (1963), 697–706.
5.
A.S.Besicovitch, On fundamental geometric properties of plane line sets, Journal of the London Mathematical Society39 (1964), 441–448.
6.
P.J.Couch, B.D.Daniel and T.H.McNicholl, Computing space-filling curves, Theory of Computing Systems50(2) (2012), 370–386.
7.
R.O.Davies, Some remarks on the Kakeya problem, Proceedings of the Cambridge Philosophical Society69 (1971), 417–421.
8.
R.Dougherty, J.H.Lutz, R.D.Mauldin and J.Teutsch, Translating the Cantor set by a random real, Transactions of the American Mathematical Society366 (2014), 3027–3041.
9.
R.Downey and D.Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, 2010.
10.
K.J.Falconer, Sections of sets of zero Lebesgue measure, Mathematika27 (1980), 90–96.
11.
K.J.Falconer, The Geometry of Fractal Sets, Cambridge University Press, 1985.
M.Fujiwara and S.Kakeya, On some problems of maxima and minima for the curve of constant breadth and the in-revolvable curve of the equilateral triangle, Tôhoku Mathematical Journal11 (1917), 92–110.
14.
X.Gu, J.H.Lutz and E.Mayordomo, Points on computable curves, in: FOCS, IEEE Computer Society, 2006, pp. 469–474.
15.
X.Gu, J.H.Lutz, E.Mayordomo and P.Moser, Dimension spectra of random subfractals of self-similar fractals, Annals of Pure and Applied Logic366(11) (2014), 1701–1726.
16.
R.C.Harkins and J.M.Hitchcock, Upward separations and weaker hypotheses in resource-bounded measure, Theoretical Computer Science389(1–2) (2007), 162–171.
17.
S.Kakeya, Some problems on maxima and minima regarding ovals, Tôhoku Science Reports6 (1917), 71–88.
18.
N.Katz and T.Tao, Recent progress on the Kakeya conjecture, in: Proceedings of the 6th International Conference on Harmonic Analysis and Partial Differential Equations, Publicacions Matematiques, 2002, pp. 161–180.
19.
B.Kjos-Hanssen and A.Nerode, Effective dimension of points visited by Brownian motion, Theoretical Computer Science410(4–5) (2009), 347–354.
20.
S.Kurtz, Randomness and genericity in the degrees of unsolvability, PhD thesis, University of Illinois at Urbana-Champaign, 1981.
21.
J.H.Lutz, Almost everywhere high nonuniform complexity, Journal of Computer and System Sciences44(2) (1992), 220–258.
22.
J.H.Lutz and E.Mayordomo, Dimensions of points in self-similar fractals, SIAM J. Comput.38(3) (2008), 1080–1112.
23.
T.H.McNicholl, The power of backtracking and the confinement of length, Proceedings of the American Mathematical Society141(3) (2013), 1041–1053.
24.
A.Nies, Computability and Randomness, Oxford Univ. Press, Inc., New York, NY, USA, 2009.
25.
O.Perron, Über einen Satz von Besicovitch, Mathematische Zeitschrift28 (1928), 383–386.
26.
R.Rettinger and X.Zheng, Points on computable curves of computable lengths, in: MFCS, R.Královic and D.Niwinski, eds, Lecture Notes in Computer Science, Vol. 5734, Springer, 2009, pp. 736–743.
27.
C.-P.Schnorr, A unified approach to the definition of a random sequence, Mathematical Systems Theory5 (1971), 246–258.
28.
C.-P.Schnorr, Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics, Vol. 218, Springer-Verlag, 1971.
29.
I.J.Schoenberg, On the Besicovitch–Perron solution of the Kakeya problem, in: Studies in Mathematical Analysis – Essays in Honour of G. Pólya, Stanford Univ. Press, Stanford, CA, 1962, pp. 383–386.
30.
J.Ville, Étude Critique de la Notion de Collectif, Gauthier-Villars, Paris, 1939.
31.
Y.Wang, Randomness and complexity, PhD thesis, University of Heidelberg, 1996.
32.
X.Zheng and R.Rettinger, Point-separable classes of simple computable planar curves, Logical Methods in Computer Science8(3) (2012), 1–19.
