В библиотеке CGAL есть реализация VD для сегментов, но она работает только для евклидовой метрики. Можно ли использовать мою собственную метрическую функцию там?
Теоретически это должно быть возможно, но нелегко сделать. Изменение метрики подразумевает изменение всех предикатов и конструкций (что довольно много работы). Вы должны предоставить новую модель SegmentDelaunayGraphTraits_2 концепции.