Wednesday, March 14, 2012

Crossing and corralling diagonals

Plane Euclidean geometry is good for mind training but research mathematicians rarely have to deal with it in their work. Here is such an occasion: the following problem has naturally appeared in my current work and will probably be included in a paper. It's not hard but I find it amusing.

Let T be a triangulation of a convex polygon P using non-crossing diagonals. So if P has n+3 sides for some n > 0, then T has n diagonals, and we identify T with this n-element set. Consider the following two ways of selecting some special subsets of T.

1. Crossing: take any diagonal d of P, and select the set of diagonals in T crossed by d (here "crossing" means having a common interior point).

2. Corralling: take any four distinct mid-points A,B,C,D of sides of P (say in a clockwise order), and select the set of diagonals in T having one end-point between B and C, and another between A and D.

Claim: these two ways of generating subsets of T are equivalent, that is, if a subset can be obtained by one of them, then it can also be obtained by another.

Solutions are welcome. If nobody finds my solution, I'll post it myself a little later.

2 comments:

rus4 said...

1->2 берем множество диагоналей, пересекающих диагональ WE, идущую с запада на восток. Тогда на множестве пересекающих ее диагоналей можно определить понятие "восточнее", и это будет линйеный порядок. Берем самые западную и восточную диагонали AB и CD, пересекающие EW, соответственно (A,C на севере, B,D на юге). Тогда любая диагональ, пересекающая EW, имеет один конец между A и C, другой между B и D.

2->1 Рассмотрим множество всех диагоналей, кроме ABCD-corralling. Они разбивают многоугольник на несколько частей. Одна из частей имеет вершины как между A и B, так и между C и D. В самом деле, иначе любая часть имеет вершины только на (не более чем) двух их четырех возможных дуг, и часть, соседняя, например, с той, в которой есть вершины с дуг AB, BC, снова будет такой же. Но должен быть какой-то способ дойти от части одного типа до части другого типа, переходя в соседние.
Так вот возьмем эту часть, соответствующие вершины назовем U,V. Диагональ UV искомая.

Но почему Вы называете это евклидовой геометрией? Это же чистая комбинаторика.

avzel said...

Федя: спасибо за решение. Вы правы, конечно, это чистая комбинаторика, просто рисование треугольников (а у меня еще и "дополнительное построение" имеется) напомнило уроки школьной геометрии.

Мое решение немножко отличается в деталях и, мне кажется, несколько попроще (но это мелочи, конечно).

1 --> 2 For every diagonal d of P, take as A and B the mid-points of two sides of P that are incident to one end-point of d, and as C and D the mid-points of two sides incident to another end-point of d. Then a diagonal is crossed by d if and only if it is corralled by A,B,C,D.

2 --> 1 Let E (resp. F) be the endpoint of some diagonal corralled by A,B,C,D, such that E is between B and C (resp. between A and D) and is closest to B (resp. to A). Then the diagonal EF belongs to T, and there is a (unique) triangle EFG of T such that G is between A and B. Similarly, let E'F'G' be a triangle of T such that E'F' is a diagonal of T corralled by A,B,C,D and closest to the segment CD, and G' is between C and D. Clearly, a diagonal is corralled by A,B,C,D if and only if it is crossed by the diagonal GG'.