Некоторые задачи и темы работ для студентов

Направление работ связано с построением и исследованием моделей пространственных тел, а также некоторых двумерных геометрических конфигураций.

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

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

Вообще для понимания сути задач можно представить их истоник. Речь идет о разнообразных технологических процессах обработки или формирования трехмерных объектов требуемой формы. В большинстве случаев это огранка драгоценных камней из исходного "сырого" камня в финальную "правильную" форму с требуемыми гранями путем шлифовки, но в принципе речь модет идти и о других технологических процессах типа станков с ЧПУ, трехмарной печати и т.п. Специфика процесса состоит в более-менее постоянном контроле того, чтоб получается на промежуточных стадиях обработки, с помощью различных фотометрических подходов, рентгеновского сканирования и т.д. Это нужно для оптимизации обработки (время, стоимость, качество), поскольку ошибки могут обходиться слишком дорого. В результате получается набор исходных данных (фотографии, сканы), по которым надо восстанавливать форму объекта и желательно "в реальном времени", т.е. нужны быстрые, точные и устойчивые алгоритмы, способные обрабатывать реальне данные с их неизбежными ошибками, неточностями и некорректностями.

Двумерные приближения

Есть множество точек на плоскости. Требуется
- построить прямую, наименее отклоняющуюся от этих точек;
- построить кривую второго порядка, наименее отклоняющуюся от этих точек;
- построить аппроксимацию этого множество набором отрезков кривых второго порядка;
- построить минимальный объемлющий прямоугольник, эллипс;
- построить выпуклую оболочку этого множества;
- построить невыпуклую оболочку этого множества с заданными условиями гладкости границы;
- провести кластеризацию этого множества по заданным критериям близости;
- выделить в этом множестве участки, хорошо прилижаемыме прямыми отрезками;

Двумерные контуры

Есть один или несколько двумерных контуров, т.е. последовательности точек, расположенных "в цепочку" друг за другом. Требуется
- для двух данных контуров найти их "усреднение";
- определить и вычислить меру близости (или различия) двух контуров;
- найти ортогональное или аффинное преобразование, совмещающее два данных контура наилучшим образом;
- аппроксимировать данный контур ломаной линией с заданной погрешностью;
- в множестве контуров найти наиболее близкий по форме к данному контуру;
- сопоставить контуры абстрактной математической модели и реального объекта.

Трехмерные приближения

Есть множество точек в пространстве. Требуется
- построить выпуклую оболочку этого множества;
- найти минимальный объемлющий эллипс, параллелипипед;
- найти плоскость, наименее удаленную от этого множества;
- найти поверхность второго порядка, наименее удаленную от этого множества;

Есть "плотное" множество точек в пространстве, полученное, например, сканированием некоторого трехмерного объекта. Требуется
- найти поверхность исходного трехмерного тела;

Есть трехмерная модель пространственного тела (многогранник). Требуется

- упростить эту модель в рамках данной точности;
- сопоставить эту модель с другой аналогичной моделью, т.е. сказать насколько они близки по форме, чем отличаются, можно ли установить соответствия между гранями моделей и т.п.;
- найти преобразование (ортогональное, аффинное), совмещающее две таких модели наилучшим образом;
- найти в модели участки поверхности, хорошо приближаемые плоскостями или поверхностями второго порядка;

Траектории

Есть объект (трехмерная модель), закрепленный в подвижном захвате, и подвижный обрабатывающий инструмент. Требуется выработать траектории движения объекта и инструмента с тем, чтобы придать объекту требуемую форму с учетом ограничений на скорости, ускорения и другие физические характеристики этой системы. Также минимизация времени обработки до нужного состояния объекта.

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