5 added 235 characters in body

I don't know that I'm quite as hooked on this problem as David S., but it really is addictive. My hunch is also that the answer should be "no," and I really really want this to be solvable by simple (if clever) combinatorial-geometry arguments. Here's some arguments of that nature which I don't think can be themselves made to go through, but which do rule out some approaches. I'm making the post community wiki, so people can add to it or correct the stupid mistakes which I've almost certainly made.

So we'll use the rectangle formulation. Suppose that S is a set of points that does intersect every sufficiently large triangle. Then if we project S onto any line, the image has to be dense. This is doable; I think that David's tau-construction has this property. But you can't build such a set up out of lattices in an easy way.

But we can do slightly better than that, although it's harder to state. You also need the projections of S intersect a strip parallel to a line L onto L to be very nicely distributed. In particular, the maximum distance between two consecutive points has to be O(1/x) for a strip of width x, which is best possible up to a constant. (To see this, notice that there are O(Lx) points in the strip, and they have to cover an interval of length L.).

By the way, this subsumes the appeals to "embedding large almost-lattices." I'd (harrison) be interested to see a set that has this stronger projection property but provably contains large rectangles. ETA: Upon further reflection, if the implied constant is uniform for all lines L, then this property's necessary and sufficient, since the projection property bounds the size of a rectangle in the complement of S that's parallel to L.

It is important to note that this rules out most straightforward random constructions. If we place N points at random on a line segment of length 1, we anticipate a gap of length log N/N somewhere. We need to do better, achieving gaps of size O(1/N). Proof: Divide the segment into N buckets. For any k consecutive buckets, the chance that they are all missed is (1-k/n)^n ~ e^{-k}. So, if k is log N + O(1), the chance that a particular k buckets are missed will be of order 1/N. Since there are on the order of N blocks of k consecutive buckets, the expected number of such blocks which are missed will be positive. So there is a positive probability of missing a segment of length log N/N.

4 I agree that those sentences were premature -- needed more sleep

I don't know that I'm quite as hooked on this problem as David S., but it really is addictive. My hunch is also that the answer should be "no," and I really really want this to be solvable by simple (if clever) combinatorial-geometry arguments. Here's some arguments of that nature which I don't think can be themselves made to go through, but which do rule out some approaches. I'm making the post community wiki, so people can add to it or correct the stupid mistakes which I've almost certainly made.

So we'll use the rectangle formulation. Suppose that S is a set of points that does intersect every sufficiently large triangle. Then if we project S onto any line, the image has to be dense. This is doable; I think that David's tau-construction has this property. But you can't build such a set up out of lattices in an easy way.

But we can do slightly better than that, although it's harder to state. You also need the projections of S intersect a strip parallel to a line L onto L to be very nicely distributed. In particular, the maximum distance between two consecutive points has to be O(1/x) for a strip of width x, which is best possible up to a constant. (To see this, notice that there are O(Lx) points in the strip, and they have to cover an interval of length L.).

I suspect that this, or a close variation on it

By the way, can be used to rule out something like David Eppstein's construction. And I think this also subsumes the appeals to "tau-construction has embedding large almost-latticesalmost-lattices." argument. I'd (I don't follow these two sentences -- David Speyer.) harrison) be interested to see a set that has this stronger projection property but provably contains large rectangles.

It is important to note that this rules out most straightforward random constructions. If we place N points at random on a line segment of length 1, we anticipate a gap of length log N/N somewhere. We need to do better, achieving gaps of size O(1/N). Proof: Divide the segment into N buckets. For any k consecutive buckets, the chance that they are all missed is (1-k/n)^n ~ e^{-k}. So, if k is log N + O(1), the chance that a particular k buckets are missed will be of order 1/N. Since there are on the order of N blocks of k consecutive buckets, the expected number of such blocks which are missed will be positive. So there is a positive probability of missing a segment of length log N/N.

3 added 665 characters in body

I don't know that I'm quite as hooked on this problem as David S., but it really is addictive. My hunch is also that the answer should be "no," and I really really want this to be solvable by simple (if clever) combinatorial-geometry arguments. Here's some arguments of that nature which I don't think can be themselves made to go through, but which do rule out some approaches. I'm making the post community wiki, so people can add to it or correct the stupid mistakes which I've almost certainly made.

So we'll use the rectangle formulation. Suppose that S is a set of points that does intersect every sufficiently large triangle. Then if we project S onto any line, the image has to be dense. This is doable; I think that David's tau-construction has this property. But you can't build such a set up out of lattices in an easy way.

But we can do slightly better than that, although it's harder to state. You also need the projections of S intersect a strip parallel to a line L onto L to be very nicely distributed. In particular, the maximum distance between two consecutive points has to be O(1/x) for a strip of width x, which is best possible up to a constant. (To see this, notice that there are O(Lx) points in the strip, and they have to cover an interval of length L -- edit by David S.)L.).

I suspect that this, or a close variation on it, can be used to rule out something like David Eppstein's construction. And I think this also subsumes the "tau-construction has large almost-lattices" argument. (Also, I think don't follow these two sentences -- David Speyer.)

It is important to note that this rules out most "random" distributions straightforward random constructions. If we place N points at random on a line segment of points.)length 1, we anticipate a gap of length log N/N somewhere. We need to do better, achieving gaps of size O(1/N). Proof: Divide the segment into N buckets. For any k consecutive buckets, the chance that they are all missed is (1-k/n)^n ~ e^{-k}. So, if k is log N + O(1), the chance that a particular k buckets are missed will be of order 1/N. Since there are on the order of N blocks of k consecutive buckets, the expected number of such blocks which are missed will be positive. So there is a positive probability of missing a segment of length log N/N.

2 added 117 characters in body