BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Cédric Pilatte appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
In this short note, we prove that the degree-three dilation of the square lattice $\mathbb{Z}^2$ is $1+\sqrt{2}$. This disproves a conjecture of Dumitrescu and Ghosh. We give a computer-assisted proof of a local-global property for the uncountable set of geometric graphs achieving the optimal dilation.
Let $S$ be a set of $n\geq 7$ points in the plane, no three of which are collinear. Suppose that $S$ determines $n+1$ directions. That is to say, the segments whose endpoints are in $S$ form $n+1$ distinct slopes. We prove that $S$ is, up to an affine transformation, equal to $n$ of the vertices of a regular $(n+1)$-gon. This result was conjectured in 1986 by R. E. Jamison. In an addendum to the paper, we show that a much stronger result can be obtained as a corollary of a structure theorem of Green and Tao on point sets spanning few ordinary lines.
We prove the NP-completeness of the following problem. Given a set $S$ of $n$ slopes and an integer $k\geq 1$, is it possible to draw a complete graph on $k$ vertices in the plane using only slopes from $S$? Equivalently, does there exist a set $K$ of $k$ points in general position such that the slope of every segment between two points of $K$ is in $S$? We then present a polynomial algorithm for this question when $n\leq 2k-c$, conditional on a conjecture of R.E. Jamison. For $n=k$, an algorithm in $\mathcal{O}(n^4)$ was proposed by Wade and Chu. For this case, our algorithm is linear and does not rely on Jamison's conjecture.