Triangle with largest area in a convex polygon
Arvind Kar
what is the fastest way (algorithm time complexity wise) to find the
triangle having the greateset area that can be formed using any 3 of
the given points?
Henry
Have you thought about this at all, and how it relates to your
previous "Triangle with maximum area using given lattice points"?
You could start by considering the maximum area of a triangle where
its base is known and the third vertex can lie on a given finite line
segment.
Martin Michael Musatov
> <arvindkar1...@gmail.com> wrote:
> > Given a set of points that represent the vertices
> of a convex polygon
> > what is the fastest way (algorithm time complexity
> wise) to find the
> > triangle having the greateset area that can be
> formed using any 3 of
> > the given points?
How do I find the time complexity T(n) and show that it is tightly bound?
Looking at the number of nested loops isn't the best way to go about getting a solution. ... I think we're trying to find the complexity of his algorithm, ...
IThe most common way of qualifying an algorithm is the Asymptotic Notation, also called Big O. ... So by ignoring the constant time complexity because it grows more slowly ... is a search algorithm that tries to find a certain value in a set of data. .... but are among the fastest sorting algorithms in practice. ...
In computer science, the complexity of an algorithm is a way to classify ... Sub-linear time algorithms (grow slower than linear time algorithms). ... To find the complexity of this algorithm, we start from the middle ...
Arvind Kar
> On 7 July, 09:30, Arvind Kar <arvindkar1...@gmail.com> wrote:
>
> > Given a set of points that represent the vertices of a convex polygon
> > what is the fastest way (algorithm time complexity wise) to find the
> > triangle having the greateset area that can be formed using any 3 of
> > the given points?
>
> Have you thought about this at all, and how it relates to your
> previous "Triangle with maximum area using given lattice points"?
I thought over this but I was unable to do better than evaluating the
area of C(n, 3) possible triangles where n is the number of vertices.
yes, I know it relates to my previous problem. if i can solve this, i
can plug the solution of this into my previous problem where convex
polygon = convex hull.
>
> You could start by considering the maximum area of a triangle where
> its base is known and the third vertex can lie on a given finite line
> segment.
yes, I know to solve this. we need to maximize the height, so we can
find a point on the finite line which is the farthest away from the
base.
could you please explain how I can know the base of the largest
triangle and how the above statement will be useful in finding the
triangle with maximum area?
James Waldby
> Given a set of points that represent the vertices of a convex polygon
> what is the fastest way (algorithm time complexity wise) to find the
> triangle having the greatest area that can be formed using any 3 of the
> given points?
I don't know what the complexity of the best method is. I'll
describe an O(h^2) method. Let the polygon be given by the set of
points {p_1, p_2, ... p_h}, numbered in clockwise consecutive order.
This paragraph states a unimodality principle. Let A,Z be any two p_i,
and suppose that A,B...Y,Z is a series of consecutive p_i that proceed
clockwise from A to Z. For any two triangles AZP, AZQ, area a(AZP) is
greater than a(AZQ) iff P is further from line AZ than is Q. Then by
convexity, the series a(AZB), a(AZC), ... a(AZY) is unimodal.
Here is a consequence of unimodality. Suppose, without loss of generality,
that no three p_i are collinear. Then only two cases can occur:
i: there exist L, M, among K,L,M,N such that LM || AZ. Then
a(AZK) < a(AZL) = a(AZM) > a(AZN). So a(AZL) and a(AZM) are maximal.
ii: there do not exist L, M, among K,L,M,N such that LM || AZ. Then
there exists L such that a(AZK) < a(AZL) > a(AZM), and a(AZL) is
maximal.
Here is the O(h^2) method.
Let A be in turn p_1, p_2, ... p_h; for each A, do following procedure:
1. Set L = next point clockwise from A, and
set Z = next point clockwise from L. (O(1))
2. Compare a(AZL) to best area so far, record if better, etc. (O(1))
3. Advance Z clockwise to next point Z'. (O(1))
4. If Z' = A, end procedure.
5. Advance L clockwise to new maximum point L'. (Because L' is between
L and A and only advances, the amortized cost of this step is O(1).)
6. Go to 2. (O(1))
Step 6 occurs h-2 times, so the procedure is O(h). The procedure is
used h times, so the method is O(h^2) overall.
--
jiw
Arvind Kar
So, here always one side is made of two adjacent points of the
polygon? (Z-L is an adjacent pair, Z'-L' is an adjacent pair) What is
the proof that the maximal triangle will always have a side made up of
two adjacent points?
What exactly is the meaning of this step:
Advance L clockwise to new maximum point L'
What do you mean by "maximum point"?
James Waldby
> On Jul 7, 9:58 pm, James Waldby ... wrote:
>> On Tue, 07 Jul 2009 01:30:55 -0700, Arvind Kar wrote:
>> > Given a set of points that represent the vertices of a convex polygon
>> > what is the fastest way (algorithm time complexity wise) to find the
>> > triangle having the greatest area that can be formed using any 3 of
>> > the given points?
>>
>> I don't know what the complexity of the best method is. I'll describe
>> an O(h^2) method. Let the polygon be given by the set of points {p_1,
>> p_2, ... p_h}, numbered in clockwise consecutive order.
>>
>> Here is the O(h^2) method.
>> Let A be in turn p_1, p_2, ... p_h; for each A, do following procedure:
>>
>> 1. Set L = next point clockwise from A, and
>> set Z = next point clockwise from L. (O(1))
>>
>> 2. Compare a(AZL) to best area so far, record if better, etc. (O(1))
>>
>> 3. Advance Z clockwise to next point Z'. (O(1))
>>
>> 4. If Z' = A, end procedure.
>>
>> 5. Advance L clockwise to new maximum point L'. (Because L' is between
>> L and A and only advances, the amortized cost of this step is
>> O(1).)
>>
>> 6. Go to 2. (O(1))
>>
>> Step 6 occurs h-2 times, so the procedure is O(h). The procedure is
>> used h times, so the method is O(h^2) overall.
> So, here always one side is made of two adjacent points of the polygon?
> (Z-L is an adjacent pair, Z'-L' is an adjacent pair)
No. In more detail, steps 5 and 6 should read:
5. Advance L clockwise to L', such that L' is most distant from
line AZ'. [It may be that L' = L.]
6. Set L to L', Z to Z', and go to 2.
Justification for 5: We know that K (the point before L) is closer
to AZ than is L. Then K is closer to AZ' than is L. To see this,
consider cases like (i) K is left of perpendiculars to AZ and AZ'
through A, (ii) K is right of perp to AZ but left of perp to AZ',
etc. K may be closer to or farther from AZ' than to AZ, but in
all cases L remains farther from both AZ and AZ' than K, hence by
unimodality we need to either stay put at L or go clockwise from
it to find a point at maximal distance from AZ'.
> What is the proof
> that the maximal triangle will always have a side made up of two
> adjacent points?
Of course that need not be so. But if it were, there would
be an obvious O(h) algorithm.
> What exactly is the meaning of this step:
>
> Advance L clockwise to new maximum point L'
>
> What do you mean by "maximum point"?
In Step 5, "maximum point" means a point p_i in the clockwise
sequence from A to Z' that is at maximal distance from line AZ'.
--
jiw
Chip Eastham
If we think about this as a convex optimization
problem, where the variables are 3 points confined
to the polygon and the objective function is the
area of their enclosed triangle, then I suspect a
pivoting strategy gives us an O(h) complexity.
Maximizing the area of the triangle must occur
with all three vertices on the boundary, since
otherwise it is possible to move a vertex not
on the boundary away from the opposing side,
thereby increasing the area.
Starting from any inscribed triangle, we check
to see if the area can be increased by "pivoting"
on one of the vertices. If we reach a local
maximum in area, convexity theory tells us we
have a global maximum.
The tricky part is to show that a particular
pivoting strategy leads to the maximum in O(h)
steps. The area is strictly increasing with
each pivot, so "cycling" is not possible. In
that the last vertex moved is already "locally"
optimal, the obvious candidate is a strategy
of pivoting on the least recently moved vertex
(until none of the three moves by consecutive
attempts).
regards, chip
James Waldby
> On Jul 7, 12:58 pm, James Waldby <n...@no.no> wrote:
>> On Tue, 07 Jul 2009 01:30:55 -0700, Arvind Kar wrote:
>> > Given a set of points that represent the vertices of a convex polygon
>> > what is the fastest way (algorithm time complexity wise) to find the
>> > triangle having the greatest area that can be formed using any 3 of
>> > the given points?
>>
>> I don't know what the complexity of the best method is. I'll describe
>> an O(h^2) method.
> If we think about this as a convex optimization problem, where the
> variables are 3 points confined to the polygon and the objective
> function is the area of their enclosed triangle, then I suspect a
> pivoting strategy gives us an O(h) complexity.
>
> Maximizing the area of the triangle must occur with all three vertices
> on the boundary, since otherwise it is possible to move a vertex not on
> the boundary away from the opposing side, thereby increasing the area.
>
> Starting from any inscribed triangle, we check to see if the area can be
> increased by "pivoting" on one of the vertices. If we reach a local
> maximum in area, convexity theory tells us we have a global maximum.
Do you have any suggested readings that explain why the latter claim
is true? I am not sure how to show it.
> The tricky part is to show that a particular pivoting strategy leads to
> the maximum in O(h) steps. The area is strictly increasing with each
> pivot, so "cycling" is not possible. In that the last vertex moved is
> already "locally" optimal, the obvious candidate is a strategy of
> pivoting on the least recently moved vertex (until none of the three
> moves by consecutive attempts).
I don't yet see how to do so, but think that strategies taking
at most O(h) pivot-on-one-vertex steps probably can be found.
What is not clear to me is whether the work per step can be O(1)
on average. It is easy to make examples where single pivot steps
take O(h) work.
--
jiw
Jake
No: Take an almost-regular hexagon. Both of the triangles formed by
taking alternating vertices are local maximums, and one of them must be
the global maximum, but you can't get from one to the other by pivoting
just one (or even two) vertices.
Arvind Kar
> On Tue, 07 Jul 2009 12:38:56 -0700, Arvind Kar wrote:
> > On Jul 7, 9:58 pm, James Waldby ... wrote:
> >> On Tue, 07 Jul 2009 01:30:55 -0700, Arvind Kar wrote:
> >> > Given a set of points that represent the vertices of a convex polygon
> >> > what is the fastest way (algorithm time complexity wise) to find the
> >> > triangle having the greatest area that can be formed using any 3 of
> >> > the given points?
>
> >> I don't know what the complexity of the best method is. I'll describe
> >> an O(h^2) method. Let the polygon be given by the set of points {p_1,
> >> p_2, ... p_h}, numbered in clockwise consecutive order.
>
> [snip unimodality principle and consequent cases]
>
>
>
>
>
>
>
> >> Here is the O(h^2) method.
> >> Let A be in turn p_1, p_2, ... p_h; for each A, do following procedure:
>
> >> 1. Set L = next point clockwise from A, and
> >> set Z = next point clockwise from L. (O(1))
In the first step do you mean setting L as the point adjacent to A in
clockwise direction. Similarly set Z as the point adjacent to L in
clockwise direction?
Chip Eastham
Hi, Jake:
You are right, your example shows we cannot pivot
monotonically to the global maximum.
--c
James Waldby
> On Jul 8, 1:57 am, James Waldby <n...@no.no> wrote:
>> On Tue, 07 Jul 2009 12:38:56 -0700, Arvind Kar wrote:
>> > On Jul 7, 9:58 pm, James Waldby ... wrote:
>> >> On Tue, 07 Jul 2009 01:30:55 -0700, Arvind Kar wrote:
>> >> > Given a set of points that represent the vertices of a convex
>> >> > polygon what is the fastest way (algorithm time complexity wise)
>> >> > to find the triangle having the greatest area that can be formed
>> >> > using any 3 of the given points?
>>
>> >> I don't know what the complexity of the best method is. I'll
>> >> describe an O(h^2) method. Let the polygon be given by the set of
>> >> points {p_1, p_2, ... p_h}, numbered in clockwise consecutive order.
...
>> >> Here is the O(h^2) method.
>> >> Let A be in turn p_1, p_2, ... p_h; for each A, do following
>> >> procedure:
>>
>> >> 1. Set L = next point clockwise from A, and
>> >> set Z = next point clockwise from L. (O(1))
>
> In the first step do you mean setting L as the point adjacent to A in
> clockwise direction. Similarly set Z as the point adjacent to L in
> clockwise direction?
Yes. For example, if A is p_5, then L is p_6 and Z is p_7 during
the first cycle within the procedure. In the second cycle,
A is p_5, Z is p_8, and L is p_6 or p_7. In the third cycle,
A is p_5, Z is p_9, and L is p_6, p_7, or p_8. And so forth,
with Z and L only moving forward (clockwise) until Z runs into A.
At that point, advance A to p_6, set L to p_7, Z to p_8, and do
the procedure again.
--
jiw
Richy
James one little doubt , how are u calculating L in O(1) time ?
What i tried was looping through all the values strictly between A and
Z and each time checking with the L found.
So suppose Z is the farthest from A in a particular case , then we
would have to loop through O(h) values each time checking for a
maximum.
Please correct me if i understood you wrong .
If there is a O(1) method to find L , letme know how?
Chip Eastham
Hi, Richy:
It is a bit tricky, but the claim is that the
average cost of finding L, spread out over all
Z's for a given A, is O(1). That's the meaning
of "amortized". Here's the idea:
A is a "1st" vertex. We start with "2nd" Z as
clockwise neighbor to A, and begin our search
for the corresponding "3rd" L = L(A,Z) with
the next clockwise neighbor to Z. There's no
immediate shortcut here; we have to try several
of vertices to find the candidate L. But what
James Waldby was pointing out with his word
"unimodal" is that area(AZL) reaches a peak
as we move L clockwise around the convex hull
and then declines. So, we can stop when we
see area(AZL') < area(AZL), for L' the next
vertex after L (note that it's possible for
two consecutive vertices at the peak to give
the same area, if LL' parallels AZ).
Then what makes his operation count work is
that when we go to check the next "2nd" vertex
for Z, say Z', we can begin the check on the
"3rd" vertex L(A,Z') with the previous choice
L that maximized area(AZL). A picture would
be a big help here, but what we're saying is
that as Z --> Z' goes clockwise around the
convex hull (but not passing A), the optimal
L(A,Z) also moves clockwise around the hull,
increasing L --> L' without passing A. We
remember which Z and L give maximum area(AZL).
For a given A, we can stop when L reaches
the vertex right before A. At this point
we will have found, for that "1st" vertex A
the maximum area of all triangles which have
A as a vertex. The number of steps taken
for A as a vertex is bounded by the number
of possible values for L, as it moves
clockwise around the hull.
Therefore, in the scheme proposed by James
Waldby, the overall complexity is O(N^2)
for N = number of vertices on convex hull,
because we simply repeat the above for
every possible A.
regards, chip
Chip Eastham
> On Tue, 07 Jul 2009 19:00:14 -0700, Chip Eastham wrote:
> > On Jul 7, 12:58 pm, James Waldby <n...@no.no> wrote:
> >> On Tue, 07 Jul 2009 01:30:55 -0700, Arvind Kar wrote:
> >> > Given a set of points that represent the vertices of a convex polygon
> >> > what is the fastest way (algorithm time complexity wise) to find the
> >> > triangle having the greatest area that can be formed using any 3 of
> >> > the given points?
>
> >> I don't know what the complexity of the best method is. I'll describe
> >> an O(h^2) method.
>
> [snip description of O(h^2) method]
>
> > If we think about this as a convex optimization problem, where the
> > variables are 3 points confined to the polygon and the objective
> > function is the area of their enclosed triangle, then I suspect a
> > pivoting strategy gives us an O(h) complexity.
>
> > Maximizing the area of the triangle must occur with all three vertices
> > on the boundary, since otherwise it is possible to move a vertex not on
> > the boundary away from the opposing side, thereby increasing the area.
>
> > Starting from any inscribed triangle, we check to see if the area can be
> > increased by "pivoting" on one of the vertices. If we reach a local
> > maximum in area, convexity theory tells us we have a global maximum.
>
> Do you have any suggested readings that explain why the latter claim
> is true? I am not sure how to show it.
What's true (as opposed to what I wrote!) is that for
convex _minimization_ problems (convex objective function
on convex feasible region) a local minimum is a global
minimum. This is ultra-straightforward: take two local
minima and look at the convex path between them, along
which by convexity the objective function has to decrease
from one of the endpoints or remain constant. (In the
first case we've contradicted the local minimum status;
in the second case we've shown the local minima share
a value and deserve to be considered global minima.)
But some better write-ups are here:
[Convex optimization -- Wikipedia]
http://en.wikipedia.org/wiki/Convex_optimization
"if a local minimum exists, then it is a global minimum."
[A tutorial on convex optimization, by H. Hindi]
http://www2.parc.com/spl/members/hhindi/reports/CvxOptTutPaper.pdf
"any local optimum is, in fact, a global optimum"
I suspect my failure in treating this as a
convex optimization problem is due in a sense to
maximizing the area, not minimizing it. I thought
this would turn out to be one of those minor
issues that has a standard workaround, e.g.
by minimzing the area outside the triangle
but inside the convex hull. But apparently
it simply isn't so, as Jake's example shows
we can have local maxima that are not global.
regards, chip
Richy
it is still slow :(
I tried another approach :
Find the vertex A with minimum 'X' coordinate and vertex B with
maximum 'X' coordinate.
Then i use the line AB as the base of my triangle and iterate through
all the other vertices to find the one which gives maximum area.
Similarly i take the base as line segment CD where vertex C and D are
the ones with minimum and maximum Y coordinate and then iterate
through all other vertices to find one which gives still greater area
if possible.
But turns out it still gives wrong answer although i myself couldn't
see as to why it is giving a wrong answer.
Regards
Richy
Chip Eastham
Hi, Richy:
Well, it may be faster but it is not the way
to find the triangle of largest area, as your
experiment confirms.
In fact consider how your approach applies to
a circle. The longest base would be that of
a diameter across the convex hull, but this
does not yield the largest triangular area.
regards, chip
Richy
Yes you are right , it wont work that way
Chip Eastham
> Hi Chip .
>
> Yes you are right , it wont work that way
The proliferation of threads in sci.math motivated
me to do a bit of research on the history of this
problem. Although not exhaustive, I did post some
information on another thread, including a link to
an open source CGAL implementation that claims
O(n log n) complexity for the largest triangle in
area on n points of a convex hull.
--c
Chip Eastham
Hi, Jake:
Your example and James' algorithm motivate the
following definition and conjecture:
We say a triangle inscribed into vertices a convex polygon
is _J-maximal_ if for each its 3 vertices V,
that triangle is of maximum area among those
which have vertex V. E.g. your slightly
irregular hexagon has exactly two J-maximal
triangles, whose vertices alternate in order
around the polygon.
The conjecture is that this is true of any
two J-maximal triangles of a convex polygon.
If true, this might help to construct a
maximum triangle in O(n log n) using some
bisection (trisection?) ideas.
regards, chip
jillbones
Conjecture: All three sides of the triangle will be diagonals of
the polygon.
Proof: Let ABM be the maximal triangle of polygon side AB. Then AHM
is greater than ABM, if H is a vertex between B & M and H is further
from AM than B.
I am not sure how to prove that there will always be an H that
is further from AM than B, but is seems axiomatic.
regards, Bill J
Jay Singh
There are multiple problems with this.
1. For a 3-sided triangle, it itself is the triangle we are looking
for. No diagonals involved.
2. Similar problem for a quadrilateral.
3. The concept can be proven wrong for polygons with higher sides too.
Imagine a large equilateral triangle with one of its corner pointing
down so that it looks the letter V with its top two end points
connected.
Now, on top of this triangle place a thin (very less height)
trapezium. The longer base of the isoceles trapezium coincides with
the top of the triangle. i.e. length of the side of the triangle =
length of the longer base of the trapezium.
What you should get is a beautiful diamond shape which is a
counterexample to your point.
James Waldby
>On Jul 12, 12:47 am, jillbones <b92...@yahoo.com> wrote:
>> > Hi, Jake:
>>
>> > Your example and James' algorithm motivate the following definition
>> > and conjecture:
>>
>> > We say a triangle inscribed into vertices a convex polygon is
>> > _J-maximal_ if for each its 3 vertices V, that triangle is of maximum
>> > area among those which have vertex V. E.g. your slightly irregular
>> > hexagon has exactly two J-maximal triangles, whose vertices alternate
>> > in order around the polygon.
>>
>> > The conjecture is that this is true of any two J-maximal triangles of
>> > a convex polygon.
Chip -- I don't understand what property "this" refers to, but if
you are suggesting that when a polygon has multiple J-maximal
triangles (JMT's), that involved vertices alternate, not so:
in the previous example (a slightly distorted hexagon), we can
add strings of arbitrarily many additional vertices between original
vertices while maintaining convexity and without adding any new
JMT's. Thus, vertices of different JMT's can be separated by O(n)
polygon points.
>> > If true, this might help to construct a maximum triangle in O(n log
>> > n) using some bisection (trisection?) ideas.
...
>> Conjecture: All three sides of the triangle will be diagonals of the
>> polygon.
>>
>> Proof: Let ABM be the maximal triangle of polygon side AB. Then AHM
>> is greater than ABM, if H is a vertex between B & M and H is further
>> from AM than B.
>>
>> I am not sure how to prove that there will always be an H that is
>> further from AM than B, but is seems axiomatic.
...
> There are multiple problems with this.
>
> 1. For a 3-sided triangle, it itself is the triangle we are looking for.
> No diagonals involved.
> 2. Similar problem for a quadrilateral. 3. The concept can be proven
> wrong for polygons with higher sides too.
>
> Imagine a large equilateral triangle with one of its corner pointing
> down so that it looks the letter V with its top two end points
> connected.
>
> Now, on top of this triangle place a thin (very less height) trapezium.
> The longer base of the isoceles trapezium coincides with the top of the
> triangle. i.e. length of the side of the triangle = length of the longer
> base of the trapezium.
>
> What you should get is a beautiful diamond shape which is a
> counterexample to your point.
Jay -
For some trapezoids (that is, trapeziums or trapezia) a counterexample
to Bill's notion does not arise. But I agree the construction can lead
to counterexamples. Here's a related example, perhaps upside down
relative to yours, and also with the trapezoid wide rather than thin,
and due to asymmetry probably not beautiful: Let the polygon be
APMQB, with A,P,M,Q,B = (0,0),(1,5),(2,9),(3,7),(4,0). The largest-
area triangle includes side AB.
--
jiw
Chip Eastham
James:
I'm not suggesting that we can't have
additional vertices on the polygon,
which of course wind up being someplace
relative to the vertices of two JMT's.
I'm conjecturing that the vertices of
the two JMT's by themselves form a
kind of "star of David" pattern.
Another way to phrase the conjecture
is that if ABC and XYZ are both JMT's,
then not all of vertices XYZ lie on
the same side of any line AB, BC, or
AC.
regards, chip
sushant
I have an idea , what if we use the technique of rotating calipers to
find all the antipodal pairs, and then for each pair test it with the
remaining vertices to see if we have a maximum?
I also tried using this similar technique which is in a way rotating
calipers only:
suppose we have a Convex Hull h with vertices arranged in
anticlockwise order
h0,h1,h2.......hm
now we start from the edge h0h1 ,
take the vertex k =h2 so vertex referred by k+1 would be vertex h3
now while ( area(h0,h1,k) <= area(h0,h1,k+1) )
increment k;
if(area(h0,h1,k) > ans
then ans = area ().....
in essence this finds the vertex k which is farthest from the edge
h0h1
now since the vertices are arranged in anticlockwise order , the
farthest vertex from the next edge starting from h0 i.e the edge
"h0h2" can only be between k and hm not before.
i.e if for example we found k = h5 for the edge h0h1 above then we
should start looking for a farthest vertex to h0h2 only from h5 till
hm.
hence we have for all the edges starting at h0 i.e h0h2,h0h3.....h0hm
for j = h2 to hm
while( area(h0,j,k) <= area(h0,j,k+1) )
increment k;
if( area( h0,j,k) > ans )
ans = area ()....
end for
This can be repeated for all starting vertices h0,h1..... till the
3rd last vertex h(m-2) but yes this doesnt not seem to be better than
N^2
repeat above for ( i=0 to m-2 )
Chip i sent you a C++ implementation of the same. Although i am almost
certain it is correct ( i used a circle analogy to prove it to
myself ) but if it is not then do try to find on what cases.
jillbones
I should have mentioned that I was talking about polygons with at
least 3 non-intersecting diagonals.
To my chagrin, I have discovered a simpler counter-example:
"One side is longer than any of the diagonals."
Another conjecture:
If there is a side-based triangle with no vertex "H"; then that
triangle is the maximal triangle of the polygon. If there is
more than one such side-based triangle, then the maximal triangle
is one of the several such side-based triangles.
regards, Bill J
jillbones
In a pentagon, every triangle must contain at least one of the sides.
regards, Bill J.