Abstract. On a triangular grid $T$ a set $H$ of triangles with vertices at grid points is called a system of triangular islands if for every pair of triangles in $H$ one of them contains the other or they do not overlap at all. Let $I_{T}$ denote the ordered set of systems of triangular islands on $T$ and let $\max(I_{T})$ denote the maximal elements of $I_{T}$. With $n + 1$ grid points on each side of $T$ define $f(n)=\max\{|H|:H \in\max (I_{T})\} $. E. K. Horváth, Z. Németh, and G. Pluhár [3] proved $(n^2+3n)/5 \leq f(n) \leq(3n^2+9n+2)/14$. For $g(n)=\min\{|H|:H \in\max (I_{T})\} $ we show $g(n)=n$ and investigate extensions to triangular grids on trapezoids and parallelograms.
AMS Subject Classification
(1991): 05A05, 05A16
Keyword(s):
maximal systems of triangular islands,
lower bound,
upper bound,
asymptotic behavior
Received July 8, 2008, and in revised form March 29, 2009. (Registered under 6418/2009.)
|