Если у вас есть координаты узлов и список ребер, то можно поступить так:

Вместо каждого ребра образуем две дуги (направленные рёбра), например, 1-8 и 8-1.

Возьмем нижнюю левую точку. Обходим внешнюю грань против часовой стрелки, выбирая самую правую исходящую дугу, здесь 1-8-9-3-13-7-6-2-10-12-14-1, удаляем дуги.

Берём любую дугу из оставшихся, обходим первую грань - опять же, выбирая самую правую исходящую дугу - например, 1-14-4-8-1 (помним, что 1-8 уже нет), удаляем дуги.

Повторяем для оставшихся дуг. В результате должно получиться F = E - V + 2 граней (включая внешнюю)

Граф ядер

Поставим точку (назовём её точкой ядра) внутри выпуклой оболочки. Упорядочим точки множества по углу вокруг этой точки. Соединим их ломаной - получится звёздный многоугольник. У него отыщем ядро (каждая сторона многоугольника задаёт полуплоскость, если их пересечь - будет ядро). Ядро - выпуклый многоугольник.

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

По новому многоугольнику строится новое ядро.

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

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

У нас есть граф, и вершина в нём. Строить целиком весь граф не нужно, у нас есть процедура поиска соседних вершин в графе (переход через ребро ядра). Этого достаточно чтобы обойти граф поиском в ширину. В каждой вершине графа известен звёздный многоугольник и его ядро.

NB Чтобы премещаться по графу (строить новые многоугольники и их ядра), точка ядра не нужна.

Сложность:

• первый многоугольник и ядро: nlogn;
• соседнее ядро (и многоугольник): nlogn (можно сократить до logn, но это сложно);
• число вершин в графе (разных многоугольников и ядер) - n⁴;
• вычисление площади n (при навигации по графу можно сократитть до константы).

Общая сложность n⁵logn.

NB Картинка в вашем вопросе имеет непосредственное отношение к графу в этом ответе. Грань на вашей картинке - ядро и вершина графа из этого ответа. Не запутайтесь в графах, их два разных. Один ваш - картинка, второй - абстрактный, двойственный к вашему.

РСДС

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

Заведём рёберный список с двойными связями (РСДС (DCEL)). Поместим в него ребра выпуклой оболочки и все выше описанные отрезки. РСДС определеляет планарный граф. Фиксируем любую грань, выберем в ней любую точку и построим звёздный многоугольник вокруг неё. Можно показать что ядро этого многоугольника совпадёт с выбранной гранью.

Другими словами, РСДС будет содержать нужный нам ядерный граф. Обойдём его в ширину вычисляя звёзды и их площади.

РСДС можно постоить за O(n⁴). За такое же время можно вычислить площади всех звёзд - площади "соседних" звёзд отличаются на фиксированное количество слагаемых.

Общая сложность - четвёртая степень, но требуется работать с РСДС.

P.S. Можно ли обойтись без полного перебора звёзд?