Учитывая DCEL, где двойник равен следующему ребру, сколько граней может иметь подразделение?

Я пытаюсь решить упражнение 2.7 из книги «Вычислительная геометрия - алгоритмы и приложения» (Берг и др.), В которой говорится

Учитывая двусвязное представление списка ребер подразделения, где Twin (e) = Next (e) выполняется для каждого полуребра e, сколько граней может иметь самое большее подразделение?

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


computational-geometry doubly-linked-list
person Paola Rossi    schedule 25.03.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я бы сказал, вы правы.

Учитывая, что Next (e) равно Twin (e) для всех полуребер e, тогда IncidentFace (Next (e)) равно IncidentFace (Twin (e)). И поскольку мы знаем, что IncidentFace (e) всегда равно IncidentFace (Next (e)), мы можем заключить, что IncidentFace (e) равняется IncidentFace (Twin (e)) для всех полуребер. Таким образом, никакое ребро не лежит на границе двух разных граней. И если никакое ребро не ограничивает две разные грани, то не может быть более одной грани.

person Andrew Durward    schedule 28.03.2013