A planar point set S is an (i, t)set of ghost chimneys if there exist lines H₀, H₁,…,H_t-1 such that the orthogonal projection of S onto H_j consists of exactly i + j distinct points. We give upper and lower bounds on the maximum value of t in an (i, t) set of ghost chimneys, showing that it is linear in i.

Preliminary version was presented at the 22nd Canadian Conference on Computational Geometry.

Keywords:

References

Adachi City, (Ghost chimneys, in Japanese), www.city.adachi.tokyo.jp/003/d10100040.html (2009) . Google Scholar
S. Skiena, J. Combinat. Theor. Ser. A 55(1), 153 (1990), DOI: 10.1016/0097-3165(90)90055-2. Web of Science, Google Scholar
J. Matoušek, A. Přívětivý and P. Škovroň, SIAM J. Discr. Math. 22(4), 1605 (2008), DOI: 10.1137/080715706. Web of Science, Google Scholar
J. Keiren , F. van Walderveen and A. Wolff , Constructability of trip-lets , Abstracts from the 25th European Workshop on Comp. Geom. ( Brussels , Belgium , 2009 ) . Google Scholar
N. J. Mitra and M. Pauly, ACM Trans. Graphics 28(5), 157 (2009). Google Scholar
L. A. Székely, Combinat. Prob. Comput. 6, 353 (1997), DOI: 10.1017/S0963548397002976. Google Scholar
J. Pachet al., Improving the crossing lemma by finding more crossings in sparse graphs, Proc. 20th Annual Symp. Comp. Geom. (2004) pp. 68–75. Google Scholar