Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Hunter, Cauchy rabbit, and optimal Kakeya sets


Authors: Yakov Babichenko, Yuval Peres, Ron Peretz, Perla Sousi and Peter Winkler
Journal: Trans. Amer. Math. Soc. 366 (2014), 5567-5586
MSC (2010): Primary 49N75; Secondary 05C57, 60G50
Published electronically: June 10, 2014
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A planar set that contains a unit segment in every direction is called a Kakeya set. We relate these sets to a game of pursuit on a cycle $ \mathbb{Z}_n$. A hunter and a rabbit move on the nodes of $ \mathbb{Z}_n$ without seeing each other. At each step, the hunter moves to a neighbouring vertex or stays in place, while the rabbit is free to jump to any node. Adler et al. (2003) provide strategies for hunter and rabbit that are optimal up to constant factors and achieve probability of capture in the first $ n$ steps of order $ 1/\log n$. We show these strategies yield a Kakeya set consisting of $ 4n$ triangles with minimal area (up to constant), namely $ \Theta (1/\log n)$. As far as we know, this is the first non-iterative construction of a boundary-optimal Kakeya set. Considering the continuum analog of the game yields a construction of a random Kakeya set from two independent standard Brownian motions $ \{B(s): s \ge 0\}$ and $ \{W(s): s \ge 0\}$. Let $ \tau _t:=\min \{s \ge 0: B(s)=t\}$. Then $ X_t=W(\tau _t)$ is a Cauchy process and $ K:=\{(a,X_t+at) : a,t \in [0,1]\}$ is a Kakeya set of zero area. The area of the $ \epsilon $-neighbourhood of $ K$ is as small as possible, i.e., almost surely of order $ \Theta (1/\vert\log \epsilon \vert)$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 49N75, 05C57, 60G50

Retrieve articles in all journals with MSC (2010): 49N75, 05C57, 60G50


Additional Information

Yakov Babichenko
Affiliation: Department of Mathematics, California Institute of Technology, Pasadena, California 91125

Yuval Peres
Affiliation: Microsoft Research, Redmond, Washington 98052

Ron Peretz
Affiliation: Department of Mathematics, London School of Economics and Political Sciences, London WC2A 2AE, United Kingdom

Perla Sousi
Affiliation: Department of Pure Mathematics, University of Cambridge, Cambridge CB3 0WB, United Kingdom

Peter Winkler
Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755

DOI: http://dx.doi.org/10.1090/S0002-9947-2014-06226-0
PII: S 0002-9947(2014)06226-0
Keywords: Pursuit games, graph games, Kakeya sets, Cauchy process
Received by editor(s): February 13, 2013
Published electronically: June 10, 2014
Additional Notes: The first author would like to acknowledge financial support by ERC 030-7950-411 and ISF 039-7679-411.
The third author’s work was supported in part by grant #212/09 of the Israel Science Foundation and by the Google Inter-university center for Electronic Markets and Auctions
The fifth author’s work was supported by Microsoft Research, by a Simons Professorship at MSRI, and by NSF grant DMS-0901475
The authors also thank MSRI, Berkeley, where part of this work was completed
Article copyright: © Copyright 2014 American Mathematical Society