Здравствуйте. Подскажите алгоритм решения этой задачки или где можно почитать на тему. 
На плоскости заданы n точек. Соеденить их непересекающимися отрезками таким образом,чтобы каждая область внутри выпуклой оболочки этого множества точек являлась треугольником

Попробуй генетичиские алгоритмы.
т.е. сначала соединяешь точки как попало, затем проверяешь, а не пересекаются ли линии, если пересекаются соединяешь по новому.
вот примерно такой цикл может помочь.

(под "внешней точкой" множества точек будем подразумевать точку, которая  отделима какой-нибудь прямой от всех остальных)
будем отсекать внешние точки по очереди:
1. находим любую внешнюю точку
2. находим все внешние точки из всех оставшихся точек области
3. из них берём одну ближайшую к первой выбраной
4. из оставшихся внешних берём ближаёшую ко второй
5. соединяем их отрезками
6. убираем первую выбранную точку из рассматриваемого множества
7. повторяем

Поищи алгоритмы триангуляции

Существует код, чтобы проверить полигон на самопеесечение.
Итак. Строим различные полигоны. Находим не самопересекающийся и разбиваем на треугольники.

ИМХО очень просто

Ну на самом деле не так уж и просто. Это действительно алгоритмы триангуляции и многие умные люди разработали разные умные алгоритмы, чтобы они работали с большим количеством точек и быстро. Мы выполняли такую задачу в рамках курса по машинной графике. Если еще актуально, могу поискать материалы, а вообще, конечно, лучше книжки умные почитать - не тривиальная, короче, задача. Давно же известно, что многие геометрические задачи на плоскости и в пространстве формулируются предельно просто, на на машинке реализуются далеко не с лету.

Про сложность не говорим. Это легко сделать полу-брутфорсом... Строим различные полигоны, проверяем на самопересечение. Нашли? Ага! Разобъем на треугольники и все.

Зачем усложнять? Провести несамопересекающуюся линию через произвольное множество точек задача сама по себе нетривиальная. Это не тот случай, когда надо вылить воду из чайника.
Алгоритм триангуляции не настолько тривиален, чтобы изложить его здесь в двух словах.
Поищи книгу (или ссылки) М. Ласло Вычислительная геометрия и компьютерная графика на C++). Там масса доступно описанных геометрических алгоритмов, в т.ч. и триангуляция Делоне. 

Решил делать так:
Нахожу выпуклый n-уголььник
Беру его вершину и провожу из нее ребра в остальные точки
Дальше перебираю треугольники, дроблю их.

Выпуклый n-угольник нахожу так:
Нахожу 4 крайние точки по y и x, строю четырехугольник.
Дальше надо узнать точка лежит за линией снаружи или внутри области.
Как это узнать?

ну вы меня удивляете. Уравнение прямой в школе проходили? Ну вот вместо равентства подставим знак "больше" или "меньше". получим уравнение полуплоскости. Затем проверим, точка в этой полуплоскости ли нет. Писать формулы не буду, ибо это надо знать и уже сто раз обсуждалось.

1) Должны ли все ребра описывающего многоугольника принадлежать треугольникам?
2) Если 3 точки (А,В,С) лежат на одной прямой - следует ли строить так, чтобы либо были соединены только А и В либо только В и С, или допустимы одновременно оба отрезка?

значит (с точки зрения программирования), нам даны их координаты

Берем первую точку (к примеру, с меньшими координатами).
По координатам вычисляем к ней две ближайших. Соединяем.
От второй точки также, от третьей... С каждым циклом, их число возрастает, ведь мы строим от каждой вершины.
Движемся по нарастанию кординат, значит, те точки, которые уже прошли, возвращаться не будут...

(дальше мысль пока ко мне не пришла)