From Circles to Generalized
Conics: Enriching the Properties
of 2D Shape Representation and
Description
PhD THESIS
submitted in partial fulfillment of the requirements for the degree of
Doctor of Technical Sciences
within the
Vienna PhD School of Informatics
by
Aysylu Gabdulkhakova
Registration Number 1029018
to the Faculty of Informatics
at the TU Wien
Advisor: Em.O.Univ.Prof.Dipl.-Ing.Dr.techn. Walter G. Kropatsch
External reviewers:
Prof. Robert Fisher. University of Edinburgh, Scotland.
Prof. Pasi Fränti. University of Eastern Finland, Finland.
Vienna, 30th June, 2022
Aysylu Gabdulkhakova Walter G. Kropatsch
Technische Universität Wien
A-1040 Wien Karlsplatz 13 Tel. +43-1-58801-0 www.tuwien.at

Declaration of Authorship
Aysylu Gabdulkhakova
I hereby declare that I have written this Doctoral Thesis independently, that I have
completely specified the utilized sources and resources and that I have definitely marked
all parts of the work - including tables, maps and figures - which belong to other works
or to the internet, literally or extracted, by referencing the source as borrowed.
Vienna, 30th June, 2022
Aysylu Gabdulkhakova
iii

Kurzfassung
Wie jede menschliche Tätigkeit ist auch Forschung mit Wissen und Erfahrung verflochten.
Ihr Ziel ist eine systematische Erforschung von Phänomenen, um die Sichtweisen und
Möglichkeiten zur Lösung eines bestimmten Problems zu erweitern. Die klassische Methode
zur Messung des Abstands zwischen zwei Objekten in Computer Vision besteht darin,
ein Paar ihrer nächstgelegenen Punkte zu finden. Bei Verwendung der euklidischen
Metrik ist die äquidistante Menge eines Punktes ein Kreis. In dieser Doktorarbeit werden
die alternativen Lösungen (mit Schwerpunkt auf dem 2D-Raum) vorgestellt, wobei die
Implikationen für die Darstellung und Beschreibung von Formen berücksichtigt werden.
Sie basieren auf anderen Arten von äquidistanten Mengen: Kegelschnitte (Ellipse und
Hyperbel) und verallgemeinerte Kegelschnitte (multifokale Ellipse und Hyperbel).
Die erste Lösung basiert auf der Tatsache, dass ein Kreis eine Ellipse mit einem Paar
zusammenfallender Brennpunkte ist. Zu den zahlreichen Eigenschaften einer Ellipse
gehört, dass die Summe der Abstände zu beiden Brennpunkten konstant ist. Sie erlaubt
eine Metrik, die den Abstand zwischen einem Punkt und einem durch die Brennpunkte
begrenzten Liniensegment findet. Alle Punkte auf diesem Liniensegment haben den
Abstand null, alle anderen Punkte, auch wenn sie auf der Gerade durch die beiden
Brennpunkte liegen, haben einen grösseren Abstand. Im Gegensatz zum klassischen Ansatz
liegt der Vorteil dieser Methode in der Berechnungseffizienz und in der Unabhängigkeit
von der Diskretisierung der Liniensegmente.
Die zweite Lösung nutzt die Haupteigenschaft von multifokalen Ellipsen – jeder Punkt hat
die gleiche Abstandssumme zur Brennpunktmenge. Dieses Konzept ist eine alternative
Definition des Abstands zwischen einem Punkt und einer Punktmenge. Eine solche
Interpretation ist wertvoll bei Optimierungsproblemen, die ihrerseits von effizienten
Bildverarbeitungstechniken profitieren können.
Die dritte Lösung findet eine Menge von Punkten, die gleich weit von zwei Objekten
entfernt sind. Dies ist wichtig bei Bildverarbeitungsverfahren wie der Skelettierung. Per
Definition enthält eine multifokale Hyperbel die Punkte, die eine konstante Differenz
zwischen den Abstandssummen zu den beiden Punktmengen aufweisen. Im Prinzip
kann der Brennpunkt eine beliebige geometrische Form haben. Dann ist die multifokale
Hyperbel mit dem zugehörigen Nullabstandswert eine gleich weit entfernte Punktmenge
zu dem Objektpaar.
v
Die Grundidee dieser Arbeit ist eine Verallgemeinerung. Ausgehend von einem Kreis,
einem Spezialfall einer Ellipse, werden verallgemeinerte Kegelschnitte betrachtet - eine
weitere konzeptionelle Erweiterung. Diese Transformation spiegelt sich in der Analyse der
geometrischen Eigenschaften dieser Kurven wieder: von den konventionellen Fakten zu den
innovativen Erkenntnissen. Dieser Ansatz ermöglicht die bestehenden und vorgeschlagenen
Methoden durch einen einzigen theoretischen Rahmen zu erklären.
Abstract
Like every type of human activity, research is intertwined with knowledge and experience.
It aims at systematic exploration of phenomena in order to expand views and possibilities
of solving a particular problem. In computer vision, the conventional way of measuring the
distance between two objects is to find a pair of closest points belonging to them. When
using the Euclidean metric, the equidistant set of a point is a circle. This thesis presents
the alternative solutions (with an emphasis on 2D space), involving the implications
for shape representation and description. They rely on other types of equidistant sets:
conics (ellipse and hyperbola) and generalized conics (multifocal ellipse and hyperbola).
The first solution rests on the fact that a circle is a special case of an ellipse, implying
a pair of coinciding focal points. Among the variety of ellipse properties, a constant
distance sum to the pair of focal points enables defining a metric. It measures the distance
between a point and a line segment bounded by the focal points. This metric defines
an increment in the line segment length when moving from one focal point to another
through the point of interest. The immediate advantages over the classical approach are
computational efficiency and independence of the line segment discretization.
The second solution exhibits the key property of multifocal ellipse – each of its points
has the same distance sum to the set of focal points. This concept alternatively defines
the distance from a point to the collection of points. Such an interpretation is valuable
in optimization problems, which can, in turn, benefit from efficient image processing
techniques for solving their tasks.
The third solution reflects a necessity in image processing techniques like skeletonization
not only to find the distance to an object but also to find a set of points that are
equidistant from a pair of objects. By definition, a multifocal hyperbola contains the
points that have a constant difference between the distance sums to the pair of point
sets. Assuming the focal point to be any geometric shape, the multifocal hyperbola with
the associated zero distance value is an equidistant set to the pair of objects.
The central notion behind this thesis is a generalization. Starting with a circle, a special
case of an ellipse, it considers a generalized conic – a further conceptual extension. This
transformation is reflected in the analysis of the geometric properties of these curves: from
the conventional facts to the innovative findings. Such an approach enables explaining the
existing and proposed methodologies through a prism of the single theoretical framework.
vii

Contents
Kurzfassung v
Abstract vii
Contents ix
List of Acronyms xiii
List of Mathematical Notations xv
1 Introduction 1
1.1 Criteria for Shape Representation . . . . . . . . . . . . . . . . . . . . . 3
1.2 Generalized Conics in Shape Representation . . . . . . . . . . . . . . . 4
1.3 Structure of the Thesis and Contributions . . . . . . . . . . . . . . . . 4
2 Conics in Analytic Geometry 7
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Conic Sections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Parabola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 Hyperbola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Confocal Conics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Generalized Conics in Analytic Geometry 15
3.1 Multifocal Ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Multifocal Hyperbola . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Confocal Generalized Conics . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 Generalized Conics with Sharp Corners . . . . . . . . . . . . . . . . . 20
3.4.1 Multifocal Ellipse with Sharp Corner . . . . . . . . . . . . . . . 20
3.4.2 Multifocal Hyperbola with Sharp Corner . . . . . . . . . . . . . 26
3.5 Changing Angle at a Corner . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5.1 Egg-Shape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5.2 Hyperbolic Shape . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
ix
4 Distance Fields based on the Properties of Generalized Conics 33
4.1 Distance from a Point to a Line Segment . . . . . . . . . . . . . . . . . 34
4.1.1 Hausdorff Distance (HD) . . . . . . . . . . . . . . . . . . . . . 34
4.1.2 Confocal-Ellipse-based Distance (CED) . . . . . . . . . . . . . 34
4.1.3 Comparison between HD and CED . . . . . . . . . . . . . . . . 36
4.2 Confocal Elliptic Field (CEF) . . . . . . . . . . . . . . . . . . . . . . . 38
4.2.1 Separating Curve . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.2 Properties of CEF . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3 Confocal Multifocal Elliptic and Hyperbolic Fields (CMEF and CMHF) 44
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5 Generating CEF, CMEF, and CMHF with Distance Transform 47
5.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2 Distance Transform (DT) . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.3 CEF in Discrete Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4 CMEF and CMHF in Discrete Space . . . . . . . . . . . . . . . . . . . 52
5.5 CEFDT under the Various Metrics . . . . . . . . . . . . . . . . . . . . 52
5.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6 Elliptic Line Voronoi Diagram (ELVD) 63
6.1 Voronoi Diagram (VD) . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.1.1 Point Voronoi Diagram (PVD) . . . . . . . . . . . . . . . . . . 65
6.1.2 Line Voronoi Diagram (LVD) . . . . . . . . . . . . . . . . . . . 65
6.1.3 Elliptic Line Voronoi Diagram (ELVD) . . . . . . . . . . . . . . 66
6.2 Comparison between PVD, LVD, and ELVD . . . . . . . . . . . . . . . 70
6.2.1 Distance Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.2.2 Types of Objects in the Site Set . . . . . . . . . . . . . . . . . 70
6.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7 Elliptic Line Voronoi Skeleton (ELVS) 79
7.1 Voronoi Skeleton (VS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7.2 Elliptic Line Voronoi Skeleton (ELVS) . . . . . . . . . . . . . . . . . . 81
7.3 Comparison between VS and ELVS . . . . . . . . . . . . . . . . . . . . 82
7.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8 Applications 91
8.1 Shape Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8.1.1 State-of-the-Art . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8.1.2 Equal-Detour-Point-based Contour Smoothing . . . . . . . . . 92
8.1.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 93
8.2 Optimal Path Planning . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.2.1 State-of-the-Art . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.2.2 Elliptic-Line-Voronoi-Diagram-based Optimal Path Planning . 95
8.2.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 96
8.3 Optimal Facility Location . . . . . . . . . . . . . . . . . . . . . . . . . 97
8.3.1 State-of-the-Art . . . . . . . . . . . . . . . . . . . . . . . . . . 97
8.3.2 Optimal Facility Location from the Generalized Conics . . . . . 97
8.3.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 98
8.4 Shape Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
9 Conclusion 101
Index 105
Bibliography 107
Curriculum Vitae 121

List of Acronyms
CED Confocal-Ellipse-based Distance. xvii, 4–6,
33–39, 50, 51, 57–59, 63, 64, 66, 69, 70, 80, 102
CEF Confocal Elliptic Field. 5, 6, 33, 38–45, 47, 48,
50, 52, 62, 98, 102
CEFDT1 Confocal Elliptic Field in terms of DT1. 53–55,
59, 62
CEFDT2 Confocal Elliptic Field in terms of DT2. 51, 52,
54, 57–62, 76, 88
CEFDT∞ Confocal Elliptic Field in terms of DT∞.
54–56, 59, 62
CEFDT Confocal Elliptic Field in terms of DT. 5, 6,
52–54, 57, 59, 62, 102
CI Center of the Incircle. 67, 69, 84
CMEF Confocal Multifocal Elliptic Field. 5, 6, 34, 44,
45, 47, 48, 50, 52, 62, 98, 102
CMEFDT2 Confocal Multifocal Elliptic Field in terms of
DT2. 52, 58, 61, 62
CMEFDT Confocal Multifocal Elliptic Field in terms of
DT. 6, 57, 59, 62, 102
CMHF Confocal Multifocal Hyperbolic Field. 5, 6, 34,
45, 47, 48, 50, 52, 62, 98, 102
CMHFDT2 Confocal Multifocal Hyperbolic Field in terms
of DT2. 52, 58, 62
CMHFDT Confocal Multifocal Hyperbolic Field in terms
of DT. 6, 57, 59, 102
DF2 Euclidean Distance Field. 38, 39, 42, 44, 45,
62, 102
DT Distance Transform. xvi, 5, 47, 49, 50, 52–54,
59, 60, 62, 80, 102
DT1 City-Block Distance Transform. 53–55, 62
xiii
DT2 Euclidean Distance Transform. xvi, 37, 49–54,
57–60, 98, 99
DT∞ Chessboard Distance Transform. 53–56, 62
EDP Equal Detour Point. 67, 69, 70, 81, 82, 92–94
ELVD Elliptic Line Voronoi Diagram. 4–6, 63–67,
69–77, 80, 81, 88, 89, 95–97, 102, 103
ELVS Elliptic Line Voronoi Skeleton. x, 5, 6, 79–89,
99, 103
HD Hausdorff Distance. xvii, 5, 34, 36, 37, 64, 70
LVD Line Voronoi Diagram. 64–66, 70–77, 81
MAT Medial Axis Transform. 80, 88
PVD Point Voronoi Diagram. 64–66, 70, 71, 74–77,
81
VD Voronoi Diagram. xvii, 4, 5, 63–66, 70, 71,
74–77, 79, 80, 88, 89, 95–97, 102
VS Voronoi Skeleton. x, 5, 79–83, 85–89, 91, 103
List of Mathematical Notations
(P, Q) Line segment defined only by the endpoints P
and Q. 39–41, 51
PQ Line segment connecting points P and Q. 8,
10, 17, 29, 36–41, 43, 44, 50, 51, 53, 55, 56, 58,
68–73, 83–85, 93
⟨, ⟩ Scalar (or dot) product. 7
C(O; r) Circle with the center at O and the radius r.
12, 69, 70, 80
E(F1, F2; a) Ellipse defined by the focal points F1 and F2
and the length of the semi-major axis a. 11,
14, 36, 37
E(a) Member of a family of confocal ellipses.
Parameter a denotes the length of the
semi-major axis. 14, 34–36
H(F1, F2; a) Hyperbola defined by the focal points F1 and
F2 and the length of the semi-transverse axis a.
12, 14
H(a) Member of a family of confocal hyperbolas.
Parameter a denotes the length of the
semi-transverse axis of a hyperbola. 14
ME(w1F1, ..., wN FN ; c) Multifocal ellipse defined by N focal points
F1, F2, ..., FN , their corresponding weights
w1, w2, ..., wN and the distance value c. 16, 21,
27–29
ME(c) Member of a family of confocal multifocal
ellipses. Parameter c denotes the total
distance sum to the focal points. 19
MH(w1F1, ..., wN FN |ν1G1, ..., νM GM ; c) Multifocal hyperbola defined by the two sets of
focal points, F = {w1F1, ..., wN FN } and
G = {ν1G1, ..., νM GM } and the distance value
c. 18, 26, 30, 31
xv
MH(c) Member of a family of confocal multifocal
hyperbolas. Parameter c denotes the absolute
difference between the distance sums to two
sets of focal points. 19, 26
P(F, l) Parabola defined by the focal point F and the
line l. 10
ε Eccentricity of a conic. 11, 13
f Half of the distance between the focal points of
an ellipse or a hyperbola. 11, 12, 14, 36, 51
a Length of the semi-major axis of an ellipse, or
length of the semi-transverse axis of a
hyperbola. 11–14, 36, 37, 51
b Length of the semi-minor axis of an ellipse, or
length of the semi-conjugate axis of a
hyperbola. 11–13, 37, 51
DF Grayscale image representing the result of DT
generated from the set of feature elements F .
49, 52
DF Distance field generated from the point F .
50–52, 60, 61
R Receptive field. 39
Sij Separating curve between the receptive fields
Ri and Rj . 39
DEF1F2 Grayscale image representing the sum of two
DT2s generated from the feature elements F1
and F2. 50, 51
DEF1F2 Grayscale image representing the normalized
sum of two DT2s generated from the feature
elements F1 and F2. The normalization is
performed by subtraction of the length of F1F2
from each pixel value. 51, 60, 61
DHF1F2 Grayscale image representing the normalized
difference of two DT2s generated from the
feature elements F1 and F2. The
normalization is performed by subtraction of
the length of F1F2 from each pixel value. 50
DR Receptive field in discrete space. 51, 61
DSij Separating curve between the receptive fields
DRi and DRj in discrete space. 51, 61
τ Threshold. 51, 60, 61
dCED(E(a1), E(a2)) Confocal-Ellipse-based Distance (CED)
between two confocal ellipses, E(a1) and E(a2).
35, 36, 38
dCED(P, l) Distance from point P to line segment l in
terms of CED. 36, 38–43, 55, 56, 66, 70
d∞(P, Q) Chessboard distance between points P and Q.
53, 56
d1(P, Q) City-Block distance between points P and Q.
52, 55
d2(P, Q) Euclidean distance between points P and Q.
8–12, 16, 18, 27–31, 34, 36, 39–44, 50, 68–70,
72, 73, 84, 85
dHD(P, l) Distance from a point P to a line segment l in
terms of HD. 34, 64
I2
binary Two-dimensional binary image. 49–52, 59, 60
IN N -dimensional digital image. 48
Z≥0 Set of non-negative integer numbers. 48
R Set of real numbers. 7, 9–14, 16–18, 20, 27, 30,
34–36, 39–43, 48, 64, 66, 67, 80
F Set of objects. 38–41, 44, 45, 49–52, 59–61, 64,
66
VDS Voronoi Diagram (VD) defined on the finite
set of sites S. 64
VR Voronoi region. 64
VRE Elliptic Line Voronoi region. 66

CHAPTER 1
Introduction
Do not disturb my circles!
Archimedes of Syracuse
Digitization of real-world objects considers simplifying their original properties in a
format that a computer can process. Among the great variety of pictorial aspects, like
color, texture, and motion, shape characterizes a silhouette. In this context, the 2D shape
is a binary image defining a projection extent of 3D object onto a 2D plane. Processing
the complete collection of shape pixels is a computationally expensive and cumbersome
procedure. Thus, the shape is commonly further simplified by selecting an appropriate
representation covering only the essential characteristics [39]. The result of this process is
known as shape representation. It plays a crucial role in a broad spectrum of applications:
document analysis, tumor recognition, analysis of particle trajectories, computer-aided
design of mechanical parts and buildings, analysis of human gait, and fingerprint/face/iris
detection [39].
The research work presented in this thesis explores the geometrical properties of conic
sections (ellipse, hyperbola) and generalized conics (egg-shape, hyperbolic shape, multifocal
ellipse, multifocal hyperbola). Such properties are analyzed from the computer vision
perspective to enrich the capabilities of existing 2D shape representation methods. For
example, one of the basic representations bounds the shape with a geometric primitive [39].
In Figure 1.1a, the shape (blue) is represented by a circle (red), which requires the center
position (green) and the radius to express the complete area of pixels. Since the shape is
elongated, the circle contains a lot of background pixels. An ellipse (Figure 1.1b) is defined
by the pair of focal points (green) and the distance value. Compared to the circle, the
ellipse better approximates the shape and reflects its orientation and elongation. Providing
the weight to one of the focal points creates an egg-shape (Figure 1.1c). It improves the
1
1. Introduction
(a) circle (b) ellipse (c) egg-shape (d) multifocal
hyperbola
Figure 1.1: Representing the shape with a primitive
ellipse representation by encoding additional semantic information – while moving from
top to bottom the shape becomes narrower. Finally, having several focal points (green)
with positive and negative weights generates a multifocal hyperbola (Figure 1.1d). In
contrast to the above primitives, it characterizes the shape concavity. In this example, the
circle is the most compact representation, whereas the ellipse, egg-shape, and multifocal
hyperbola contain less outliers and provide more semantic information.
Any point in space is mapped to the unique ellipse generated from the given pair of
points [66]. This geometric property is used to compute a distance from a point to a line
segment. Figure 1.2 illustrates two house shapes (blue). The wall is approximated by the
line segment bounded with the red circles. Assuming the endpoints of the line segment as
focal points enables associating each pixel with a distance value of the ellipse that passes
through it (left house in Figure 1.2). Traditionally, the line segment is expressed by its
points. The distance values propagate from these points as circles, and each pixel is
associated with the circle having the smallest radius (right house in Figure 1.2). The clear
benefits of the ellipse-based metric are the independence of sampling and computational
simplicity. The applications include space tessellation (Chapter 6), shape representation
with skeletons (Chapter 7), and optimal path planning (Chapter 8). In addition, the
ellipse-based metric enriches the classical representations by reflecting the relative line
segment length.
Figure 1.2: Distance from the house wall. The colors indicate various distance values
2
1.1. Criteria for Shape Representation
1.1 Criteria for Shape Representation
A vast number of shape representation methods in the literature are broadly classified
as contour-based and region-based [92, 123, 189]. The distinction lies in using points
on the shape boundary [20, 134] or also in its interior [25, 26, 158]. Costa et al. [39]
distinguish the third group of approaches – transform-based. They cover techniques such
as Fourier transform and represent the shape by the transform coefficients. Assuming the
possibility of shape reconstruction from its representation, the methods are categorized as
information preserving and information non-preserving [39,92]. The shape representation
provides a basis for extracting semantically meaningful information for characterization,
classification, or recognition. A process of collecting quantitative information about
the object from its representation is called shape description or characterization. A
selection of shape descriptor is influenced by the requirements of particular applications,
desirable shape properties, and subjective factors, such as preferences and experience
of researchers. The shape descriptors involve numeric characteristics, like an area, a
perimeter, a thickness, a curvature of parts, and many more, which reasonably represent
sufficient and relevant information for further analysis.
Several authors defined a set of criteria to support systematic evaluation of various shape
representations. The considered properties express qualitative, rather than quantitative,
measures. Marr and Nishihara [95] emphasize the properties related to computational
parameters (accessibility), robustness (sensitivity, stability), and applicability (scope and
uniqueness) of methods. Brady [30] focuses on the relation between global and local
representations by considering characteristics such as rich local support, propagation,
smooth extension and subsumption. Yang et al. [184] provide the requirements for efficiency
and perceptual similarity with human intuition. Regarding the existing evaluation
schemes [30,95,184], this thesis takes the following criteria into consideration:
• scope of the representation defining the shape classes where the corresponding
technique is applicable;
• uniqueness indicating the presence of one-to-one mapping between the shape
representation/description and the shape;
• invariance to transformations, such as translation, rotation, and scaling;
• stability/robustness to the impact of noise and occlusions;
• accuracy to preserve subtle shape details;
• efficiency in terms of computational complexity;
• abstraction of the representation to multiple scales or hierarchical levels.
3
1. Introduction
1.2 Generalized Conics in Shape Representation
This thesis introduces the region- and contour-based shape representation and description
concepts that rely on the geometric properties of conics and their generalizations. It
explains the existing and proposed methods within the single theoretical framework. The
central source of inspiration behind this work is the generalization property of ellipse: it
can degenerate into a point, a line segment, and a circle. The metric Confocal-Ellipse-
based Distance (CED) uses this property to measure the distance between a point and a
line segment (Chapter 4-5).
CED provides valuable advantages over the classical space tessellation approach called
Voronoi Diagram (VD) (Chapter 6). For example, the proposed Elliptic Line Voronoi
Diagram (ELVD) avoids the decomposition of line segments with common endpoint since
the obtained Voronoi edge does not contain an area. ELVD is a representation that
implicitly prioritizes the acute angles and comparably long line segments. This property
mitigates the effect of outliers and noise in skeletonization (Chapter 7) and is beneficial
in the applications such as optimal path planning and contour smoothing (Chapter 8).
The conic sections are extendable by considering infinitely many focal points, resulting
in the powerful geometric object called generalized conic (Chapter 3). The discovered
and derived properties broaden the scopes of shape representation and description. For
instance, the new types of primitives, namely an egg-shape and a hyperbolic shape with
corner, expand the possibilities to represent the shape. Compared to the ellipse, they
require only one additional parameter – a weight at one of the focal points. Another
example adopts the convexity property of multifocal ellipse to solve the optimization
problems, such as optimal facility location (Chapter 8).
1.3 Structure of the Thesis and Contributions
The formalization of real-world scenarios in computer vision enforces a transition from
continuous to discrete space. In particular, discrete geometry is a study of combinatorial,
geometric, and topological properties of objects like points, lines, rectangles, ellipses,
spheres, and cubes that are used in contrast to smooth surfaces [34]. Digital geometry is a
branch of discrete geometry that has an expanding role in computer vision and computer
graphics. It analyzes digitized objects (for instance, two-dimensional (2D) images and
three-dimensional (3D) samples of the surface of the scanned objects) from the point of
graph-theoretical and combinatorial concepts [79].
The necessity to develop computationally efficient algorithms and data structures for
inherently geometric problems gave rise to computational geometry as an independent
discipline in the 1970s. The fundamental concepts developed in this field are successfully
used in various domains: robotics, computer graphics, geographic information systems,
computer-aided design and manufacturing, and pattern recognition [40]. As a result, the
term computational geometry has multiple domain-specific connotations [48, 52, 53, 99,
103, 131,152]. In this thesis, the definition is adopted from [131] and [152] and considers
4
1.3. Structure of the Thesis and Contributions
a systematic study of data structures and algorithms for geometric problems from the
point of their computational complexity. The synergy of the two disciplines, discrete and
computational geometry, bridges the gap between mathematics and computer science [43].
For a problem that is geometric in nature, a successful application-driven solution takes
two considerations into account [40]:
1. Understanding of geometric properties that are useful for the given problem.
2. Finding the appropriate data structures and algorithmic techniques that enable
efficient usage of the above properties.
In relation to the thesis, Chapter 2 starts with the formal definitions of the basic
mathematical notions that are sufficient for following the discussion. It further introduces
the conic sections and their relevant properties. Chapter 3 expands the discussion towards
the generalized conics. It presents not only the facts mentioned in the existing literature
but also the geometric findings with a practical value in the computer vision domain.
Chapter 4 discusses the proposed metric, the Confocal-Ellipse-based Distance (CED),
that computes the distance between a point and a line segment. Its properties are
analyzed through a comparison with the classical approach, the Hausdorff Distance (HD).
Afterwards, the chapter explores the properties of the distance field, the Confocal Elliptic
Field (CEF), that relies on CED as a proximity measure. Eventually, the properties of
generalized conics provide a basis for the creation of the Confocal Multifocal Elliptic
Field (CMEF) and the Confocal Multifocal Hyperbolic Field (CMHF).
Chapter 5 establishes a connection between CEF and digital space. To compute the
distance fields, the classical image processing technique, called Distance Transform (DT),
is applied. In this regard, the resultant representation has the name Confocal Elliptic
Field in terms of DT (CEFDT). Due to the discrete nature of the approach, the properties
of the original CEF are revisited. The underlying concept behind CEFDT is not limited
to the use of the Euclidean distance. Therefore, CEFDT is discussed in relation to the
metric impact on the resultant representation after substituting the Euclidean distance
with City-Block and Chessboard.
Chapters 6 and 7 gain a deeper insight into the properties of CEF. The proposed Elliptic
Line Voronoi Diagram (ELVD) and Elliptic Line Voronoi Skeleton (ELVS) are considered
generalizations of the classical Voronoi Diagram (VD) and Voronoi Skeleton (VS).
The presented theoretical findings have a potential to be applied in the computer vision
domain. Chapter 8 exemplifies the practical problems where the advantage of the
developed techniques can be vividly illustrated.
5
1. Introduction
This thesis summarizes the research work published in proceedings of the international
conferences together with additional findings that improve understanding of the content:
1. Aysylu Gabdulkhakova, Walter G. Kropatsch: Confocal Ellipse-based Distance and
Confocal Elliptical Field for polygonal shapes. In Proceedings of the International
Conference on Pattern Recognition, pages 3025–3030, 2018 [56]
2. Aysylu Gabdulkhakova, Maximilian Langer, Bernhard W. Langer, Walter G.
Kropatsch: Line Voronoi Diagrams Using Elliptical Distances. In Proceedings of
the Joint IAPR International Workshop on Structural, Syntactic, and Statistical
Pattern Recognition, pages 258–267, 2018 [59]
3. Aysylu Gabdulkhakova, Walter G. Kropatsch: Generalized conics: properties and
applications. In Proceedings of the International Conference on Pattern Recognition,
pages 10728–10735, 2020 [57]
4. Aysylu Gabdulkhakova, Walter G. Kropatsch: Generalized conics with the sharp
corners. In Proceedings of the Iberoamerican Congress on Pattern Recognition,
pages 419–429, 2021 [58]
The present work covers a wide range of topics starting with the theoretical discussions
and finishing with the practical applications. Despite such a variety, the core value behind
this thesis is the introduction of the generalized conics into the field of computer vision.
Specifically, the contributions can be listed as follows:
1. study of the geometric properties of conic sections and generalized conics;
2. analysis of the egg-shape and hyperbolic shape with corners, and introduction of
the method for deriving their parameters;
3. introduction of the metric CED and analysis of its properties;
4. introduction of the distance fields CEF, CMEF, and CMHF;
5. introduction of the discrete distance fields CEFDT, CMEFDT, and CMHFDT;
6. analysis of CEFDT under City-Block and Chessboard distances;
7. reconsideration of CEF from the point of ELVD and analysis of the properties;
8. reconsideration of CEF from the point of ELVS and analysis of the properties;
9. comparison of the proposed representations with the state-of-the-art;
10. demonstration of the computer vision applications using the derived concepts.
6
CHAPTER 2
Conics in Analytic Geometry
This chapter covers the mathematical notions and properties underlying this research
work. In the beginning, it introduces the basic concepts that give a solid foundation to
follow the discussion about conics with a special emphasis on an ellipse and a hyperbola.
The description of each type of conics accounts for nomenclature and geometric properties.
In particular, the definitions of ellipse and hyperbola are the keystones to the proposed
metric, whereas the concept of confocal conics - to the proposed distance field. Despite the
variety of geometry branches, here, the focus is on the Euclidean and analytic geometry
which are necessary for computer vision.
2.1 Preliminaries
This section briefly introduces the definitions and notations that facilitate understanding
of the work.
Definition 1 (Euclidean space). Euclidean space is the finite N-dimensional vector space,
RN , with a scalar (or dot) product. The scalar product is a function ⟨, ⟩ : RN × RN → R,
such that for any elements x, y, z ∈ RN the following axioms hold true:
1. ⟨x, y⟩ = ⟨y, x⟩ – symmetry
2. ⟨x + z, y⟩ = ⟨x, y⟩ + ⟨z, y⟩ – distributivity
3. ⟨αx, y⟩ = α⟨x, y⟩, α ∈ R – linearity in the first argument
4. ⟨x, x⟩ ≥ 0, ⟨x, x⟩ = 0 ⇔ x = 0 – positive-definiteness
Definition 2 (Point). A point P is a primitive notion in the Euclidean space that has
no dimensional attributes, like length, area, or volume.
7
2. Conics in Analytic Geometry
Definition 3 (Line segment). A line segment PQ is a straight path connecting a pair of
points P and Q. It has a one-dimensional attribute which is a length.
A coordinate system is a method that enables defining the position of a point in space
numerically. Such a concept makes it possible to solve geometric problems analytically.
Definition 4 (Cartesian coordinates). A Cartesian coordinate system (also called
rectangular coordinates) defines N mutually perpendicular axes with the common origin
O. A point is defined by an N-tuple of real numbers P = (p1, p2, ..., pN ), called coordinates,
that express the signed distances from the origin.
The Euclidean distance (also referred to as L2-metric) measures the line segment length
in the Cartesian coordinates.
Definition 5 (Euclidean distance). The Euclidean distance between two points in the
Euclidean space, P = (p1, p2, ..., pN ) and Q = (q1, q2, ..., qN ), is defined as:
d2(P, Q) = (p1 − q1)2 + (p2 − q2)2 + ... + (pN − qN )2 (2.1)
Definition 6 (Barycentric coordinates). A barycentric coordinate system defines a
point with the reference to an N -simplex expressed by the vertices V1, V2, . . . , VN+1. If
placing the masses m1, m2, ..., mN+1 at the vertices makes P the center of mass of the
N -simplex (or the barycenter), then the (N + 1)-tuple (m1 : m2 : ... : mN+1) is called
homogeneous barycentric coordinates.
Property 1 (Multiplying the barycentric coordinates by a non-zero constant). The
points P = (m1 : m2 : ... : mN+1) and Q = (km1 : km2 : ... : kmN+1) are the same, thus,
multiplying the barycentric coordinates by the non-zero scalar value k has no effect [38].
Property 2 (Geometric interpretation of the barycentric coordinates). Assume that
P = (mA : mB : mC) is the barycenter of the 2-simplex formed by the vertices A, B, and C
with the corresponding masses mA, mB, and mC . The areas of the sub-triangles △PBC,
△PAC, and △PAB are proportional to the barycentric coordinates of P (Figure 2.1) [38].
Figure 2.1: Interpreting the barycentric coordinates by the areas of sub-triangles
8
2.2. Conic Sections
Definition 7 (Metric). A metric is a function RN = RN × RN → R such that every two
elements X, Y ∈ RN are associated with a unique non-negative number, which satisfies
the following conditions (axioms of the metric space):
1. non-negativity: ρ(X, Y ) ≥ 0
2. identity of indiscernibles: ρ(X, Y ) = 0 ⇐⇒ X = Y
3. symmetry: ρ(X, Y ) = ρ(Y, X)
4. subadditivity or triangle inequality: ρ(X, Y ) + ρ(Y, Z) ≥ ρ(X, Z), ∀Z ∈ RN
Definition 8 (Level set). A level set is defined by the points where the given function
takes on a particular value.
2.2 Conic Sections
The classical definition of conic sections, or conics, considers the intersection of a plane
with one or two nappes of a cone [66]:
Definition 9 (Conic section). A conic section, or a conic, is a curve formed at the
intersection of a double napped cone with a plane that does not pass through its vertex.
Slicing one nappe produces either an ellipse (Figure 2.2a) or a parabola (Figure 2.2c).
A circle is a special case of the ellipse, obtained by cutting the nappe perpendicularly
to the cone axis (Figure 2.2b). The plane intersection with both nappes creates a
hyperbola (Figure 2.2d). In this thesis, a focus is on the ellipse and hyperbola.
(a) ellipse (b) circle (c) parabola (d) hyperbola
Figure 2.2: The conic sections
2.2.1 Parabola
Visually, a parabola is a U -shaped curve that is mirror-symmetric with regard to some
axis (Figure 2.3a). Here, l expresses a fixed line called directrix, while F is a fixed point
called focus. The point V , called vertex, is an intersection between the parabola and
its symmetry axis. The line segment between the focus and the vertex, f = d2(F, V ),
defines the focal distance. Consider now the formal definition of this conic section.
9
2. Conics in Analytic Geometry
Definition 10 (Parabola). A parabola, denoted as P(F, l), is the locus of points equidistant
from both - the focus F and the directrix l:
P(F, l) = {P ∈ R2 : d2(P, F ) = inf{d2(P, L) | L ∈ l}} (2.2)
(a) translation by (x0, y0) (b) counterclockwise rotation by α
Figure 2.3: The parabola in the 2D Cartesian coordinate system
This is illustrated in Figure 2.3a. Let V be the vertex, P - an arbitrary point of the
parabola, F - the focus, l - the directrix. Then, Definition 10 leads to the following
equalities: d2(V, L1) = d2(V, F ) and d2(P, L2) = d2(P, F ). Note, the shortest path
connecting a point and a line is perpendicular to that line [106], or V L1⊥l and PL2⊥l.
Implicit Representation
The parabola rotated by the angle θ in the counterclockwise direction with the vertex
V (x0, y0), as shown in Figure 2.3b, is implicitly defined as:
((x − x0) sin α + (y − y0) cos α)2 = 4f((x − x0) cos α − (y − y0) sin α) (2.3)
Explicit Representation
Alternatively, the parabola is defined in the parametric form:
x − x0 = ft(t cos α − 2 sin α)
y − y0 = ft(t sin α + 2 cos α)
, (2.4)
where t is a parameter that ranges from −∞ to +∞.
10
2.2. Conic Sections
(a) translation by (x0, y0) (b) counterclockwise rotation by α
Figure 2.4: The ellipse in the 2D Cartesian coordinate system
2.2.2 Ellipse
The ellipse in the 2D Cartesian coordinate system is shown in Figure 2.4a. It has two
axes, major and minor, that intersect at the center O. The major axis has a length of 2a
and passes through the focal points F1 and F2, which are located symmetrically at the
distance f from the center. The minor axis is perpendicular to the major axis and has a
length of 2b. Formally this type of conic is defined below.
Definition 11 (Ellipse). An ellipse, denoted as E(F1, F2; a), is the locus of points such
that the sum of their distances to two focal points F1 and F2 is constant:
E(F1, F2; a) = {P ∈ R2 : d2(P, F1) + d2(P, F2) = 2a} (2.5)
In turn, the following equation makes a link between the parameters a, b, and f :
a2 = b2 + f2 (2.6)
Another way to relate these parameters is connected to the notion of eccentricity, denoted
as ε. It shows the degree of ellipse elongation and is formally defined as:
0 ≤ ε = a2 − b2
a
= f
a
< 1 (2.7)
As follows from (2.6) and (2.7), the length of the semi-major axis satisfies the condition
a > f = 1
2d2(F1, F2). In the special cases, the ellipse degenerates into a circle (f = 0,
ε = 0, b = a) and into a line segment (f → a, ε → 1, b → 0).
11
2. Conics in Analytic Geometry
Definition 12 (Circle). A circle, denoted as C(O; r), is the locus of points which distance
to the point O is constant:
C(O; r) = {P ∈ R2 : d2(P, O) = r} (2.8)
Implicit Representation
Consider the ellipse in the 2D Cartesian coordinate system rotated by the angle α in the
counterclockwise direction about its center at O(x0, y0) (Figure 2.4b). Then, each point
P (x, y) ∈ R2 of the ellipse satisfies the following equation:
((x − x0) cos α − (y − y0) sin α)2
a2 + ((x − x0) sin α + (y − y0) cos α)2
b2 = 1 (2.9)
Explicit Representation
Alternatively, the ellipse is parametrically defined as:
x − x0 = a cos θ cos α − b sin θ sin α
y − y0 = a cos θ sin α + b sin θ cos α
, (2.10)
where θ is a parameter that ranges from 0 to 2π.
2.2.3 Hyperbola
As illustrated in Figure 2.5a, the hyperbola contains two non-intersecting curves, called
branches [66]. Observe the shortest line segment connecting the branches. Its two
endpoints, V1 and V2, are called vertices, and its midpoint O is called center. Notice
the two lines intersecting each other at the center. While moving away from the center,
they approach the hyperbola branches. These lines are called asymptotes. The hyperbola
has two axes: transverse and conjugate [91]. The transverse axis is formed by the line
segment connecting the vertices V1 and V2. This line segment has a length of 2a. The
conjugate axis is perpendicular to the transverse axis. Here, b is the distance between
the vertex and intersection point of the two lines: the asymptote and tangent to the
hyperbola branch passing through that vertex. The focal points, F1 and F2, belong to
the line containing the vertices. They are symmetric to each other with respect to the
center. The half of the distance between the focal points is denoted as f . The hyperbola
branches are symmetric regarding the transverse and conjugate axes [66].
Definition 13 (Hyperbola). A hyperbola, denoted as H(F1, F2; a), is the locus of points
with the constant absolute difference between the distances to the focal points F1 and F2:
H(F1, F2; a) = {P ∈ R2 : |d2(P, F1) − d2(P, F2)| = 2a } (2.11)
Compared to the ellipse (2.6), the parameter relation between a, b, and f is:
f2 = a2 + b2 (2.12)
12
2.2. Conic Sections
(a) translation by (x0, y0) (b) counterclockwise rotation by α
Figure 2.5: The hyperbola in the 2D Cartesian coordinate system
The eccentricity value of hyperbola, ε, is computed as:
1 < ε = a2 + b2
a
= f
a
(2.13)
When ε tends to 1, the branches flatten along the line containing the transverse axis.
With the growth of ε to infinity, the branches approach lines parallel to the conjugate
axis until they degenerate into the line.
Property 3. The tangent to hyperbola branch at the vertex is perpendicular to the
transverse axis [91].
Implicit Representation
Assume the hyperbola rotated by α degrees in the counterclockwise direction about its
center at O(x0, y0) (Figure 2.5b). Each of its points P (x, y) ∈ R2 satisfies the equation:
((x − x0) cos α − (y − y0) sin α)2
a2 − ((x − x0) sin α + (y − y0) cos α)2
b2 = 1 (2.14)
Explicit Representation
The parametric form defining the hyperbola is:
x − x0 = ±a cosh θ cos α − b sinh θ sin α
y − y0 = ±a cosh θ sin α + b sinh θ cos α
, (2.15)
where the parameter θ ∈ R.
13
2. Conics in Analytic Geometry
(a) confocal conics (b) orthogonality of the tangents at P
Figure 2.6: The confocal ellipses (solid) and hyperbolas (dashed) from the focal points
F1 and F2. Here, P is an intersection point of the ellipse and the hyperbola
2.3 Confocal Conics
The previous section discusses each conic section and its properties individually. Here, in
contrast, the focus is on a family of conics that share the same focal points and have
various associated sums of the distances (Figure 2.6a).
Definition 14 (Confocal ellipses (hyperbolas)). The ellipses (hyperbolas) sharing the
common focal points, F1 and F2, are called confocal ellipses (hyperbolas).
As follows from Definition 14, when related to the confocal ellipses (hyperbolas), the
original ellipse or hyperbola notation E(F1, F2; a)/H(F1, F2; a) is simplified by using only
the parameter a. In other words, E(a)/H(a) respectively.
Property 4 (Uniqueness of confocal ellipse and hyperbola passing through a point).
Given any point P ∈ R2 there is exactly one level set from the family of confocal
ellipses (hyperbolas) that passes through it [66]:
a>f
E(a) = R2 (2.16)
0<a<f
H(a) = R2 (2.17)
Property 5 (Confocal ellipse and hyperbola intersect orthogonally). The tangents
to the confocal ellipse and hyperbola at the point of their intersection are mutually
orthogonal [66] (Figure 2.6b).
According to Properties 4 and 5, the families of confocal ellipses and hyperbolas form the
orthogonal coordinate system, called elliptic coordinate system [66]. It has an application
in, for instance, astronomy [41] and physics [164,172].
14
CHAPTER 3
Generalized Conics in
Analytic Geometry
This section is based on the following publications:
Aysylu Gabdulkhakova, Walter G. Kropatsch:
Generalized conics: properties and applications. In Proceedings of the International
Conference on Pattern Recognition, pages 10728–10735, 2020 [57]
Aysylu Gabdulkhakova, Walter G. Kropatsch:
Generalized conics with the sharp corners. In Proceedings of the Iberoamerican Congress
on Pattern Recognition, pages 419–429, 2021 [58]
The conics can be generalized into a class of higher-order curves by taking infinitely many
focal points. Each focal point is associated with a real number that reflects its weight.
It is the usual definition of generalized conics [63,101,130,150]. In the literature, there
is a variety of other generalizations. For instance, Nagy et al. [108, 177] introduce an
additional division by the number of focal points and defined the level sets by the average
distances to the set of focal points. Glaeser et al. [60] consider the weighted distance
sums, as well as the weighted sums of distance products.
From the point of naming conventions, various authors refer to the generalized conics
as polyconics [101] or multifocal curves [60]. For the constant weighted distance sums,
there exist works about polyellipses [101], multifocal ellipses [50, 60], n-ellipses [150],
Tschirnhaus´sche Kurven [170], k-ellipses [112], egglipses [143], and ovals [97]. For the
constant absolute differences of weighted sums, there are references to generalized [63]
and multifocal [60] hyperbolas. This thesis respects the following nomenclature. The
generalized conics denote a class of curves that extends the properties of conics to infinitely
many focal points. To distinguish various types of the generalized conics and emphasize
15
3. Generalized Conics in Analytic Geometry
(a) w1 = w2 = w3 = 1 (b) w1 = 0.8, w2 = 0.2, and w3 = 1
Figure 3.1: The multifocal ellipses, having the form ME(w1F1, w2F2, w3F3; c), that pass
through the point P in the 2D Cartesian coordinate system
the fact of having multiple focal points, it is proposed to use the terms multifocal ellipse
and multifocal hyperbola.
The original motivation to study the topic appeared in the mathematical community.
Nowadays, the generalized conics are applied in approximation theory [50], optimization
problems [174,175,180], geometric tomography [177], and architecture [126]. This chapter
discusses the geometrical properties of multifocal ellipses and hyperbolas, and presents
the findings from the shape representation perspective.
3.1 Multifocal Ellipse
Definition 15 (Multifocal ellipse). A multifocal ellipse, ME(w1F1, ..., wN FN ; c), is a
generalization of the ellipse (the weights w1, w2, ..., wN are positive real numbers). It is a
locus of points with a constant weighted distance sum to its N focal points:
ME(w1F1, ..., wN FN ; c) = {P ∈ R2 :
N
i=1
wid2(P, Fi) = c} (3.1)
Figure 3.1 shows the multifocal ellipses from the three focal points, F1, F2, and F3. Here,
an arbitrary point P ∈ R2 plays the anchor role in the exemplification of the respective
level set. Observe the change of the multifocal ellipse passing through P , when the focal
points have identical (Figure 3.1a) and various (Figure 3.1b) weights.
Property 6 (Convexity and compactness of multifocal ellipse). ME(w1F1, ..., wN FN ; c)
is convex and compact [119].
Property 7 (Global minimum for non-collinear focal points). (3.1) reaches the global
minimum at one point when the focal points are non-collinear [119] (the point M in
Figure 3.2a).
16
3.1. Multifocal Ellipse
(a) non-collinear foci: at M (b) odd number of collinear foci: at F3
(c) even number of collinear foci: at F3F4
Figure 3.2: The global minimum (minima) for the various sets of focal points
Property 8 (Global minimum for odd number of collinear focal points). (3.1) reaches
the global minimum at F N+1
2
if N is an odd number of ordered collinear focal points [119,
150] (the point F3 in Figure 3.2b).
Property 9 (Global minimum for even number of collinear focal points). (3.1) reaches
the global minimum at all points of F N
2
FN
2 +1 if N is an even number of ordered collinear
focal points [150] (the line segment F3F4 in Figure 3.2c).
When dividing (3.1) by N , every point is mapped to the weighted arithmetic mean
distance to the given set of focal points [108]. Together with Properties 6 to 9 it makes
the multifocal ellipses useful for optimization tasks, such as Fermat-Torricelli [174,175]
and Weber [180] problem. In the literature, this task is also referred to as an optimal
facility location problem [21] and is featured in Section 8.3.
Property 10 (Multifocal ellipse tends to a circle at infinity). The multifocal ellipse
approaches a circle when it infinitely grows in size.
Property 10 stems from the observation that every focal point inside a finite area of R2
has the same distance to the points infinitely far away in space. Thus, these points are
17
3. Generalized Conics in Analytic Geometry
(a) w1 = w2 = ν1 = 1 (b) w1 = 0.8, w2 = 0.2, and ν1 = 1
Figure 3.3: The multifocal hyperbolas, having the form MH(w1F1, w2F2|ν1G1; c), that
pass through the point P in the 2D Cartesian coordinate system
perceived as one. Eventually, with regard to (3.1), the multifocal ellipse that is defined
from a single focal point approaches a circle.
3.2 Multifocal Hyperbola
Definition 16 (Multifocal hyperbola). A multifocal hyperbola is a generalization of
a hyperbola, MH(w1F1, ..., wN FN |ν1G1, ..., νM GM ; c). It is defined on two sets of focal
points with positive weights. The multifocal hyperbola expresses a locus of points such
that the following absolute difference of the distance sums remains constant:
MH(w1F1, ..., wN FN |ν1G1, ..., νM GM ; c) =
{P ∈ R2 : |
N
i=1
wid2(P, Fi) −
M
j=1
νjd2(P, Gj)| = c} (3.2)
For simplicity, the points F1, ..., FN are referred to as positively weighted, and the points
G1, ..., GM – as negatively weighted.
Figure 3.3 demonstrates the examples of multifocal hyperbolas. The first set of focal
points contains F1 and F2, whereas the second set – G1. The level sets are passing
through the arbitrary point P ∈ R2. Notice the difference between Figures 3.3a and 3.3b
caused by the weights at the focal points. As can be concluded from (3.1) and (3.2), a
multifocal hyperbola is a multifocal ellipse that accepts weights with the opposite signs,
namely plus and minus. Nevertheless, this statement is questionable, and Properties 6
to 9 are not fulfilled for the multifocal hyperbola.
Let F = {w1F1, ..., wN FN } and G = {ν1G1, ..., νM GM } denote the sets of focal points.
By omitting the absolute value in (3.2), the multifocal hyperbola expresses the space
tessellation. The points with positive values are closer to G; the points with negative
values – closer to F ; the points with zero values are equidistant to both sets, F and G.
18
3.3. Confocal Generalized Conics
As can be noted from Definition 15 and 16, the multifocal ellipse defined by the set
J = F ∪ G has several associated multifocal hyperbolas depending on the sampling.
Property 11 (Number of multifocal hyperbolas for N focal points). For the set of N
focal points, there exist (2N−1 − 1) multifocal hyperbolas.
Proof. Each focal point belongs to one of the two groups. So the problem of finding the
number of multifocal hyperbolas reduces to the combinatorial task of splitting the set
into two non-intersecting subsets. Together, such subsets form the original set. Each of
them contains at least one and at most N − 1 elements. The order of the elements does
not matter. The number of k-combinations of an N -element set, for 1 ≤ k ≤ N − 1, is:
N−1
k=1
N
k
=
N
k=0
N
k
− N
N
− N
0 (3.3)
According to the properties of binomial coefficients, N
N = N
0 = 1 and
N
k=0
N
k = 2N [32].
Next, (3.3) shows the total number of subsets of the N -element set, excluding the
situations when one subset is empty or contains all elements. The initial problem searches
for the pairs of subsets forming the original set. Selecting k elements is the same as
not selecting N − k elements. The symmetry property [32] states that N
k = N
N−k . In
relation to the initial problem, (3.3) is divided by two. In other words, the number of
multifocal hyperbolas for the set of N focal points equals:
N−1
k=1
N
k
2 = 2N−1 − 1 (3.4)
3.3 Confocal Generalized Conics
Similar to Section 2.3, it is possible to define confocal multifocal ellipses and hyperbolas.
Definition 17 (Confocal multifocal ellipses (hyperbolas)). Multifocal ellipses (hyperbolas)
sharing the common focal points and their corresponding weights are called confocal
multifocal ellipses (hyperbolas).
The original notations of multifocal ellipse (hyperbola) can be simplified by using only
one parameter, c, that defines the distance value: ME(c)/MH(c) correspondingly.
Property 12 (Uniqueness of confocal multifocal ellipse and hyperbola passing through
a point). Given any point P ∈ R2, there is exactly one level set from a family of confocal
multifocal ellipses (hyperbolas) that passes through it.
19
3. Generalized Conics in Analytic Geometry
(a) confocal multifocal conics (b) angle between the tangents at P
Figure 3.4: The confocal multifocal ellipses (solid) and hyperbolas (dashed) from the
focal points F1 and F2 with the weights w1 = 0.7 and w2 = 1 correspondingly. The point
P is taken arbitrarily
As opposed to conics, Property 5 is not necessarily met in the case of families of confocal
multifocal ellipses and hyperbolas. For example, in Figure 3.4b, the angle formed by the
tangents to the multifocal ellipse and hyperbola at the point P is not right.
3.4 Generalized Conics with Sharp Corners
From the shape representation perspective, it is important to have a formal description
of curves that can be potentially generated. This section focuses on the situation when
the level sets contain sharp corners.
Definition 18 (Corner). A point of a curve, where the left-hand tangent differs from the
right-hand tangent, is called corner.
To simplify the discussion about the properties, it is proposed to normalize the weights.
Each of the N weights is divided by the maximum value among them, max(w1, w2, . . . , wN ):
wi = wi
max(w1, w2, . . . , wN ) , i ∈ [1 . . . N ] (3.5)
Hence, the weight values range in the half-closed interval (0, 1].
3.4.1 Multifocal Ellipse with Sharp Corner
Property 13 (Location of a corner in a multifocal ellipse). If a multifocal ellipse has a
corner, it is located only at the focal point. Such a level set is expressed either by a closed
curve with a corner or by a closed sequence of arcs with multiple corners.
Proof. As stated in Definition 15, each point P = (x, y) of the multifocal ellipse is mapped
to the weighted distance sum to the N -element set of focal points. Let Fi = (xi, yi) be
20
3.4. Generalized Conics with Sharp Corners
the i-th focal point, i ∈ [1 . . . N ]. Hence, (3.1) is expressed with regard to (2.1) as:
ME(w1F1, ..., wN FN ; c) =
N
i=1
wi (x − xi)2 + (y − yi)2 (3.6)
(3.6) defines a continuous function that is not differentiable at P coinciding with one
of the focal points (same reasoning for the non-weighted case is in [112]). Thus, when
present, the corner is at the focal point.
Consider the example. Figure 3.5a illustrates three level sets generated from the focal
points F1, F2, and F3 with the respective weights w1, w2, and w3. Each of these level sets
is a closed curve with the corner at one of the focal points. When changing the values of
weights (Figure 3.5b), the focal points F1 and F3 become connected by a closed sequence
of arcs and form the level set with two corners at F1 and F3. In Figure 3.5c, the focal
points F1, F2, and F3 express the corners of the level set containing a closed set of arcs.
Similarly, in Figure 3.5d, the focal points F1, F2, and F3 correspond to the corners of the
same level set. The focal point F4 corresponds to the global minimum, thus, its level set
contains only the point F4 and no corner.
Definition 19 (Convex hull). Given a set of points, the convex hull is its smallest convex
subset that encloses all the elements.
Property 14 (Number of corners in a multifocal ellipse). A multifocal ellipse from N
focal points can have up to N corners passing through that focal points.
Proof. As Property 13 states, the corner is located only at the focal point. Thus, the
number of corners cannot exceed the number of focal points. In the case of a single focal
point, there exist no level set with a corner. According to Property 6, the multifocal
ellipse is convex. Hence, when the focal points form the convex hull, it is possible to
generate up to N corners in the same level set. The focal points outside the convex hull
are either a global minimum or a part of a different level set. It results in less than N
corners in the same level set.
For instance, let the multifocal ellipse contain three focal points forming the convex hull.
Varying the weights generates the level sets containing one (Figure 3.5a), two (Figure 3.5b),
and three (Figure 3.5c) corners. In general, the maximum number of corners connected
by a single level set equals the number of focal points forming a convex hull (Figure 3.5d).
Here, the focal point F4 is inside the convex hull and is the global minimum.
Property 15 (Uniqueness of weights in a multifocal ellipse passing through all the focal
points). Consider a set of N focal points forming a convex hull. There exists a unique
set of normalized weights that corresponds to the multifocal ellipse passing through all
these focal points.
21
3. Generalized Conics in Analytic Geometry
(a) w1 = w2 = w3 = 1 (b) w1 = 0.46, w2 = 1, w3 = 0.93
(c) w1 = 0.608, w2 = 0.8298, w3 = 1 (d) w1 = 0.4625, w2 = 1, w3 = 0.75, w4 = 1
Figure 3.5: The multifocal ellipses with the corners at the focal points
Proof. Property 15 can be proven by induction.
1. N = 1 : Consider a multifocal ellipse containing a single focal point. According to
the normalization strategy, its weight w is always 1. Thus, Property 15 holds true.
2. N = 2 : Consider a pair of focal points with the normalized weights w1 and w2,
where w1 = 1. The level set connecting the focal points has the distance value D.
The distance between the focal points is l. Then, according to (3.1):
w1 · 0 + w2 · l = D
w1 · l + w2 · 0 = D
⇐⇒ w2 · l = D
w2 · 0 = D − l
(3.7)
The above system of linear equations can be expressed in a matrix form:
l
0 w2

= D
D − l
(3.8)
The system of linear equations has a unique solution if the matrix rank equals the
number of unknown variables. So does the rank of the augmented matrix [110]. The
22
3.4. Generalized Conics with Sharp Corners
Figure 3.6: The triangle formed by the focal points F1, F2, and F3
rank of the matrix in (3.8) is 1 since the last row contains zero. It suffices to prove
that the rank of the augmented matrix also equals 1. By definition, the rank equals
the number of rows of the largest submatrix with a non-zero determinant [110]:
l D
0 D − l
(3.9)
As can be seen, it is an upper-triangular matrix. Its determinant equals the product
of the main diagonal elements [110]. Hence, the system of linear equations does
not have any solution if (D − l) · l ̸= 0. Since l is greater than 0, the equality to
zero is achieved when (D − l) = 0, or D = l. It is a unique solution corresponding
to the ellipse that is degenerated into a line segment.
3. N = 3 : Consider the triplet of focal points with the normalized weights w1, w2,
and w3, where w1 = 1. Let l1, l2, and l3 express the pairwise distances between the
focal points (Figure 3.6), and D to be the distance value of the level set connecting
them. The corresponding system of linear equations is:

w1 · 0 + w2 · l1 + w3 · l2 = D
w1 · l1 + w2 · 0 + w3 · l3 = D
w1 · l2 + w2 · l3 + w3 · 0 = D
⇐⇒

w2 · l1 + w3 · l2 = D
w2 · 0 + w3 · l3 = D − l1
w2 · l3 + w3 · 0 = D − l2
(3.10)
(3.10) in the matrix form is expressed as:
l1 l2
0 l3
l3 0
 w2
w3
=
 D
D − l1
D − l2
 (3.11)
23
3. Generalized Conics in Analytic Geometry
First, the rank of the matrix is computed as follows:l1 l2
0 l3
l3 0
 | · 1
l1| · 1
l3| · 1
l3
(3.12a)
⇒
1 l2
l1
0 1
1 0

←−
−1
+
(3.12b)
⇒
1 l2
l1
0 1
0 − l2
l1

| ·− l1
l2
(3.12c)
⇒
1 l2
l1
0 1
0 1
 (3.12d)
In (3.12d), the last line can be removed. It leads to the rank being equal to 2.
Second, by applying the same operations, the augmented matrix becomes:l1 l2 D
0 l3 D − l1
l3 0 D − l2
 (3.13a)
⇒

1 l2
l1
D
l1
0 1 D−l1
l3
1 0 D−l2
l3

←−
−1
+
(3.13b)
⇒

1 l2
l1
D
l1
0 1 D−l1
l3
0 − l2
l1
D−l2
l3
− D
l1

| · l1
l2
(3.13c)
⇒

1 l2
l1
D
l1
0 1 D−l1
l3
0 −1 ( D−l2
l3
− D
l1
) · l1
l2

←−+
(3.13d)
⇒

1 l2
l1
D
l1
0 1 D−l1
l3
0 0 ( D−l2
l3
− D
l1
) · l1
l2
+ D−l1
l3
 (3.13e)
The determinant equals the product of the diagonal elements [110]. Thus, the
unique solution is obtained when:
(D − l2
l3
− D
l1
) · l1
l2
+ D − l1
l3
= 0 ⇐⇒ D = 2l1l2
l1 + l2 − l3
(3.14)
Otherwise, there is no solution.
24
3.4. Generalized Conics with Sharp Corners
4. N = k + 1 : Assume Property 15 is true for N = k. So, the augmented matrix is:

1 l12 l13 . . . l1k D1
0 1 l23 . . . l2k D2
. . .
0 0 0 . . . 1 Dk−1
0 0 0 . . . 0 Dk
 (3.15)
Here, Di is the distance value, and lmn is the variable coefficient after applying the
Gaussian elimination [110], 1 ≤ i, n ≤ k, 1 ≤ m ≤ k − 2. There is the unique level
set passing through k focal points, only if Dk = 0, otherwise – no solution.
Adding the extra column and row in (3.15) corresponding to the (k + 1)st focal
point results in:

1 l12 l13 . . . l1k l1k+1 D1
0 1 l23 . . . l2k l2k+1 D2
. . .
0 0 0 . . . 1 lk−1k+1 Dk−1
0 0 0 . . . 0 lkk+1 Dk
lk+11 lk+12 lk+13 . . . lk+1k 0 Dk+1
 | · 1
lkk+1
(3.16a)
⇒

1 l12 l13 . . . l1k l1k+1 D1
0 1 l23 . . . l2k l2k+1 D2
. . .
0 0 0 . . . 1 lk−1k+1 Dk−1
0 0 0 . . . 0 1 Dk
lkk+1
lk+11 lk+12 lk+13 . . . lk+1k 0 Dk+1

(3.16b)
As observed in (3.16b), the variable coefficients in the last row can be eliminated
by consecutive multiplication-subtraction of the above k rows:

1 l12 l13 . . . l1k l1k+1 D1
0 1 l23 . . . l2k l2k+1 D2
. . .
0 0 0 . . . 1 lk−1k+1 Dk−1
0 0 0 . . . 0 1 Dk
lkk+1
0 0 0 . . . 0 0 D′
k+1

(3.17)
Subsequently, if D′
k+1 = 0, there is only one combination of the normalized weights
{1, w2, . . . , wk+1}, such that the multifocal ellipse connects all (k + 1) focal points.
Otherwise, such a level set does not exist.
25
3. Generalized Conics in Analytic Geometry
3.4.2 Multifocal Hyperbola with Sharp Corner
As opposed to multifocal ellipses, which generate convex level sets, multifocal hyperbolas
enable getting concave corners. Let F = {w1F1, w2F2} and G = {ν1G1} be the sets
of focal points producing the confocal multifocal hyperbolas (Figure 3.7). One of the
level sets, MH(cG1), contains a concave corner at G1. Another level set, MH(cF1), passes
through F1 and has the convex corner at that focal point. Eventually, the level set
corresponding to F2, MH(cF2), is the focal point itself.
Figure 3.7: The confocal multifocal hyperbolas with the corners at F1 and G1
Property 16 (Multifocal hyperbola containing a focal point and a curve). A multifocal
hyperbola can contain a focal point and a curve that are not connected.
This statement is exemplified in Figure 3.8. In the presence of negatively weighted focal
points, the same distance value is present in multiple disconnected regions. Consider
the two sets of focal points: F = {w1F1, w2F2, w3F3} and G = {ν1G1}. Each member of
the family of confocal multifocal hyperbolas is denoted as MH(w1F1, w2F2, w3F3|ν1G1; c).
Let the level set passing through F1 be denoted as MH(cF1), through F2 – MH(cF2),
through F3 – MH(cF3), and, eventually, through G1 – MH(cG1). The 3D representation
of the level sets has two axes that define the spatial location of the points and one
axis – their distance value (Figure 3.8a). Figure 3.8b shows the top view on the level
sets passing through the focal points. In this scenario, the positively weighted focal
points (F1, F2, and F3) are the local/global minima, whereas G1 is the local maximum.
As can be observed, the level set passing through the global minimum F2 contains only
the focal point itself. The distance value of the local minimum F3 is also present in the
region surrounding F2. Hence, the level set MH(cF3) has two disconnected components:
the point F3 and the curve around F2. The level set passing through F1 contains also
the curve surrounding F2 and F3. Finally, the level set MH(cG1) contains the focal point
G1 and the curve surrounding all the positively weighted focal points.
Property 17 (Multifocal hyperbola does not pass through all the focal points). There
is no multifocal hyperbola connecting all positively and negatively weighted focal points.
Property 17 stems from the fact that a multifocal hyperbola maps each point in space to
either of the two multifocal ellipses. As a result, there can be no level set connecting
26
3.5. Changing Angle at a Corner
(a) confocal multifocal hyperbolas in 3D (b) level sets (top view)
Figure 3.8: The confocal multifocal hyperbolas passing through the focal points
positively and negatively weighted points simultaneously. In this case, one of the level
sets would cross the zero-curve – the level set containing the points equidistant to both
multifocal ellipses. Eventually, the point(s) at the intersection would be associated with
two distance values, which is not possible because of Property 12.
3.5 Changing Angle at a Corner
The complexity of generalized conics increases with a number of focal points. For example,
the degree of polynomial defining the multifocal ellipse with N focal points equals 2N if
N is odd, and 2N − N
N/2 if N is even [112]. The existing works derive the parameters of
generalized conics in the special cases, such as egglipse [143]. This section discusses the
multifocal ellipses and hyperbolas that are generated from a pair of weighted focal points,
namely an egg-shape and a hyperbolic shape (Figure 3.9). In particular, it establishes
the formal correspondence between the angles and weights at corners.
3.5.1 Egg-Shape
According to (3.1), the multifocal ellipse with the pair of focal points F1 and F2 and the
respective weights w1 and w2 can be defined as:
ME(w1F1, w2F2; c) = {P ∈ R2 : w1d2(P, F1) + w2d2(P, F2) = c} (3.18)
After normalization (3.5), there remains a single weight parameter 0 < µ = min(w1,w2)
max(w1,w2) ≤ 1.
Assume that the smaller weight corresponds to F2, then:
ME(F1, µF2; c) = {P ∈ R2 : d2(P, F1) + µd2(P, F2) = c} (3.19)
Besides the special case, when the multifocal ellipses are ellipses (µ = 1), the level sets
resemble an egg-shape with various sharpness.
27
3. Generalized Conics in Analytic Geometry
(a) the egg-shape having the sharp corner
at F2, α = 62◦, µ = 0.47
(b) the hyperbolic shape having the sharp corner
at F2, β = 118◦, µ = 0.47
Figure 3.9: The egg-shape and the hyperbolic shape with the focal points at F1 and F2.
The lower half shows the level sets, and the upper half shows the curve parameters
Figure 3.9a exemplifies the level sets generated from the pair of focal points F1 and F2,
where the latter has the weight µ = 0.47. The level set with the corner passes through
the focal point F2. The angle at the corner equals 2α = 124◦.
Theorem 1 (Global minimum for an egg-shape). (3.19) reaches the global minimum at
the focal point with the largest associated weight.
Proof. Assume the egg-shape, ME(F1, µF2; c), where 0 < µ < 1. To prove the theorem,
estimate the distance value of an arbitrary point P depending on its location (Figure 3.10):
1. P is located to the left of F1: d2(P, F1) + µd2(P, F2)
2. P is located at F1: µd2(F1, F2)
3. P is located between F1 and F2: d2(P, F1) + µd2(P, F2)
4. P is located at F2: d2(F1, F2)
5. P is located to the right of F2: d2(P, F1) + µd2(P, F2)
Proof by contradiction. Let the global minimum be located not at F1, but at some point
P to the left of F1 (case 1). The distance value at P must be less than at F1:
d2(P, F1) + µd2(P, F2) < µd2(F1, F2) (3.20)
Since P is located to the left of F1, the angle F2F1P ranges from 90◦ to 180◦. By
the triangle property [125], the longest side is opposite to the largest angle, thus,
µd2(P, F2) > µd2(F1, F2). When applied to (3.20), d2(P, F1) becomes negative which is
28
3.5. Changing Angle at a Corner
Figure 3.10: The regions, where an arbitrary point P is located relatively to F1 and F2
a contradiction. Similarly, it is possible to show that the global minimum cannot be
located to the right of F2 (case 5).
Let P be in the region bounded by the half-planes passing through F1 and F2 (case 3). If
P belongs to the line segment F1F2, then d2(P, F1)+µd2(P, F2) > µd2(F1, F2) since µ < 1.
Otherwise, P and the focal points form a triangle. According to the triangle inequality [34],
d2(P, F1) + d2(P, F2) > d2(F1, F2). Hence, d2(P, F1) + µd2(P, F2) > µd2(F1, F2).
Finally, P cannot be located at F2 (case 4) since d2(F1, F2) > µd2(F1, F2).
As can be observed, the minimum value among all the regions is achieved when the point
P coincides with the focal point F1 (case 2).
Theorem 2 (Angle at a corner of an egg-shape). Consider the egg-shape ME(F1, µF2; c)
with the sharp corner. The normalized weight (µ) of the focal point F2 equals approximately
the cosine of half of the angle at the corner (α).
Proof. Let ME(F1, µF2; c) be the egg-shape that has the sharp corner at F2 (Figure 3.9a).
Here, F1 and F2 are the focal points, P is infinitely close to F2 and is a part of the corner.
Assume the following notations: d2(F1, P ) = n, d2(F2, P ) = m, d2(F1, F2) = 2f , and
F1F2P = α. According to Definition 15, all points of the egg-shape are mapped to the
same distance value. It equals the length of the line segment F1F2:
d2(F1, F2) + µd2(F2, F2) = d2(F1, F2) = 2f (3.21)
Consider now substituting P in (3.21):
d2(F1, P ) + µd2(F2, P ) = 2f (3.22)
n + µm = 2f (3.23)
=⇒ n = 2f − µm (3.24)
By considering the triangle △F1PF2 and the law of cosines [128], it is possible to derive
the alternative estimate of n:
m2 + 4f2 − 4mf cos α = n2 (3.25)
29
3. Generalized Conics in Analytic Geometry
Substitution of n estimate from (3.24) in (3.25) results in:
m2 + 4f2 − 4mf cos α = 4f2 − 4µmf + m2µ2 (3.26)
=⇒ m = 4f(µ − cos α)
µ2 − 1 (3.27)
As discussed, the point P is infinitely close to F2 in continuous space. So, in discrete
space, the length of m converges to zero. It leads to further simplification of (3.27):
m = 4f(µ − cos α)
µ2 − 1 = 0 (3.28)
=⇒ µ = cos α (3.29)
(3.29) establishes the direct dependency between the angle at the corner of the egg-shape
and the weight of the corresponding focal point.
Theorem 2 enables rewriting (3.19) by considering the angle 2α at the corner:
d2(F1, P ) + cos α · d2(F2, P ) = d2(F1, F2) (3.30)
On one side, (3.30) has an important implication for shape representation: compared to
the ellipse, the egg-shape has one additional parameter which explicitly defines the angle
at its corner. On the other side, it is possible to derive the parameters of the egg-shape
with the corner if the curve satisfies (3.30). Refer to Figure 3.9a. The symmetry axis
passes through F2 and bisects the corner creating two congruent angles α. The point M
is the intersection point of the symmetry axis and the egg-shape. This information is
sufficient to derive the distance between the focal points by substituting M in (3.30):
d2(F1, F2) = d2(M, F2) · (1 + cos α)
2 (3.31)
Finally, F1 can be found as the point on the symmetry axis that is inside the egg-shape
at the distance d2(F1, F2) from F2.
3.5.2 Hyperbolic Shape
Analogically to the egg-shape, it is possible to formalize the correspondence between the
angle and the weight at a corner of a hyperbolic shape. According to (3.2), the weighted
multifocal hyperbola with two focal points, F1 and F2, and their respective weights, w1
and w2, can be defined as follows:
MH(w1F1|w2F2; c) = {P ∈ R2 : |w1d2(P, F1) − w2d2(P, F2)| = c} (3.32)
Using the normalization strategy (3.5) enables keeping only the single weight parameter
0 < µ = min(w1,w2)
max(w1,w2) ≤ 1. In particular, when µ = 1, the level sets are hyperbolas. Assume
the smaller weight corresponds to the point F2 (Figure 3.9b), then (3.32) becomes:
MH(F1|µF2; c) = {P ∈ R2 : |d2(P, F1) − µd2(P, F2)| = c} (3.33)
30
3.5. Changing Angle at a Corner
Theorem 3 (Angle at a corner of a hyperbolic shape). Consider the hyperbolic shape
MH(F1|µF2; c) with the corner. The normalized weight (µ) of the focal point F2 equals
approximately minus the cosine of half of the angle at the corner (β).
Proof. Let MH(F1|µF2; c) be the hyperbolic shape with the corner at F2 (Figure 3.9b).
The point P is infinitely close to F2 and belongs to the corner. Consider the following
notations: d2(F1, P ) = n, d2(F2, P ) = m, d2(F1, F2) = 2f , and F1F2P = β. According
to (3.33), the distance value at F2 equals:
|d2(F1, F2) − µd2(F2, F2)| = d2(F1, F2) = 2f (3.34)
Analogically to the proof for the egg-shape, get the estimate of n by substituting the
point P in (3.34):
n = 2f + µm (3.35)
Similarly, consider the law of cosines [128] for the triangle △F1PF2 and substitute n by
the estimate from (3.35). It leads to the following relation:
m = −4f(µ + cos β)
µ2 − 1 (3.36)
Since m is infinitely small, it is possible to assign it to zero in discrete space: µ = − cos β.
As a result, the angle at the corner of the hyperbolic shape has the direct dependency on
the weight of the corresponding focal point.
One implication of Theorem 3 is the possibility to rewrite (3.33) more intuitively. If the
angle at the concave corner equals 2β, then the level set passing through the corresponding
focal point F2 satisfies:
d2(F1, P ) + cos β · d2(F2, P ) = d2(F1, F2) (3.37)
Another implication is connected to the shape representation domain. Compared to the
ellipse, the hyperbolic shape generated from the pair of focal points requires only one
additional parameter – the angle at the corner. Hence, given a curve that satisfies (3.37),
it is possible to derive its parameters. Consider the level set illustrated in Figure 3.9b.
The symmetry axis intersects the hyperbolic shape at F2 and M and bisects the corner
creating a pair of congruent angles β. Then, the distance between the focal points
according to (3.37) equals:
d2(F1, F2) = d2(M, F2) · (1 + cos β)
2 (3.38)
Consequently, the remaining focal point F1 is at the distance d2(F1, F2) when moving
along the symmetry axis from F2 to M . Apparently, there is a similarity between (3.31)
and (3.38). Although, the convexity of the egg-shape implies a positive cos α, whereas
the concavity in the hyperbolic shape requires a negative cos β.
31
3. Generalized Conics in Analytic Geometry
3.6 Summary
A number of focal points highly influences the complexity of generalized conics. It implies
the idea of focusing on particular scenarios prior to creating a general picture. This
chapter limits the scope of analysis to multifocal ellipses and hyperbolas with corners.
In the case of an egg-shape (or a hyperbolic shape), the established correspondence
between the angle at the corner and the weight of the focal point broadens the view on
shape representation with ellipses. The correspondence between the weights of more
than two focal points and the angles at the corners is the question for future research.
The uniqueness of the normalized weights passing through all the focal points of the
multifocal ellipse is a potential key to tackle that problem. Also, imagine an iterative
refinement of the level set in order to match the given shape. The research question, in
this case, relates to the impact of each focal point. Especially, if adding the focal point
causes a local or a global change in the level sets. Finally, in accordance to the elliptic
coordinate system, it would be of interest to investigate a coordinate system based on
confocal multifocal ellipses and hyperbolas.
32
CHAPTER 4
Distance Fields based on the
Properties of Generalized Conics
This chapter is based on the following publications:
Aysylu Gabdulkhakova, Walter G. Kropatsch:
Confocal Ellipse-based Distance and Confocal Elliptical Field for polygonal shapes. In
Proceedings of the International Conference on Pattern Recognition, pages 3025–3030,
2018 [56]
Aysylu Gabdulkhakova, Maximilian Langer, Bernhard W. Langer, Walter G. Kropatsch:
Line Voronoi Diagrams Using Elliptical Distances. In Proceedings of the Joint IAPR
International Workshop on Structural, Syntactic, and Statistical Pattern Recognition,
pages 258–267, 2018 [59]
Aysylu Gabdulkhakova, Walter G. Kropatsch:
Generalized conics: properties and applications. In Proceedings of the International
Conference on Pattern Recognition, pages 10728–10735, 2020 [57]
A distance field is an implicit space representation. It specifies for each point its proximity
to a set of objects with regard to a distance function [24]. The existing approaches
measure the distance between a pair of points. The object or its boundary is decomposed
into a set of points, and the proximity is the distance to the closest element from this set.
The present work provides the alternative views to this problem. First, the Confocal-
Ellipse-based Distance (CED) measures the distance between a pair of confocal ellipses
which, in turn, can degenerate into a point or a line segment. It enables computing
the distance between the point and the line segment by defining the latter only by its
endpoints. A part of this chapter analyzes the geometrical properties of the distance field
generated from CED – the Confocal Elliptic Field (CEF).
33
4. Distance Fields based on the Properties of Generalized Conics
Second, by referring to the generalized conics, the proximity to the set of objects can
be measured as the distance sum to all objects in this set. This idea is reflected in the
Confocal Multifocal Elliptic Field (CMEF). The difference between two CMEFs produces
the Confocal Multifocal Hyperbolic Field (CMHF) expressing the proximity to the pair
of object sets.
4.1 Distance from a Point to a Line Segment
This section presents the new metric for computing the distance between a point and a
line segment based on the properties of confocal ellipses. The comparison with the state-
of-the-art approach, the Hausdorff Distance (HD), regards a distance value distribution.
4.1.1 Hausdorff Distance (HD)
A classical way to measure the distance between a point and a line segment is to use the
Hausdorff Distance (HD).
Definition 20 (Hausdorff Distance). The Hausdorff Distance (HD) between an arbitrary
point P ∈ R2 and the line segment l equals the shortest distance between P and any point
L ∈ l with regard to a selected metric (for instance, Euclidean):
dHD(P, l) = inf{d2(P, L) | L ∈ l} (4.1)
Figure 4.1 shows the resultant distribution of the HD distance values. Let the line
segment l contain N points, l = {L1, . . . , LN }. The intuition of the level set is a fusion
of the circles with the given radii (r1 or r2) and the centers at Li, i ∈ [1 . . . N ].
Figure 4.1: The distribution of the HD distance values
4.1.2 Confocal-Ellipse-based Distance (CED)
According to Property 4 of confocal ellipses, it is ensured that each point on a 2D plane
has a single distance value associated with it. This fact enables introducing a metric.
Definition 21 (Confocal-Ellipse-based Distance). The distance between the points of two
confocal ellipses, E(a1) and E(a2), is called the Confocal-Ellipse-based Distance (CED),
34
4.1. Distance from a Point to a Line Segment
dCED : R2 × R2 → R. It is an absolute difference between the lengths of major axes, 2a1
and 2a2, of these ellipses:
dCED(E(a1), E(a2)) = 2|a1 − a2| (4.2)
Theorem 4 (CED is a metric). CED is a metric.
Proof. Consider E(a1) and E(a2) to be confocal ellipses. According to Definition 7, the
proposed distance must satisfy the metric conditions:
1. non-negativity, dCED(E(a1), E(a2)) ≥ 0
By definition, the absolute value is non-negative. Thus, 2|a1 − a2| ≥ 0.
2. identity of indiscernibles, dCED(E(a1), E(a2)) = 0 ⇔ E(a1) = E(a2)
a) Let dCED(E(a1), E(a2)) = 0.
Then: 2|a1 − a2| = 0 =⇒ a1 = a2 =⇒ E(a1) = E(a2).
b) Let E(a1) = E(a2).
Then: a1 = a2 =⇒ 2|a1 − a2| = 0 =⇒ dCED(E(a1), E(a2)) = 0.
3. symmetry, dCED(E(a1), E(a2)) = dCED(E(a2), E(a1))
By definition, dCED(E(a1), E(a2)) = 2|a1 − a2| = 2|a2 − a1| = dCED(E(a2), E(a1)).
4. subadditivity, dCED(E(a1), E(a2)) ≤ dCED(E(a1), E(a3)) + dCED(E(a2), E(a3))
2|a1 − a2| ≤ 2|a1 − a3| + 2|a2 − a3|
Substitution of the absolute values by respecting the value correspondence leads to
valid inequalities. Hence, the subadditivity property is met.
Figure 4.2: The distribution of the CED distance values
35
4. Distance Fields based on the Properties of Generalized Conics
A special case of CED relates to measuring the distance from a point to a line segment.
According to (2.5), an ellipse degenerates into a line segment when the major axis length
equals the focal distance. The line segment is defined by its endpoints, taken as focal
points. In (4.2), let one of the confocal ellipses, for example, E(a2), be the line segment
connecting its focal points F1 and F2. Hence, a2 = f . Then, for each point on E(a1), the
distance to any point on E(a2) with regard to CED equals:
dCED(E(a1), E(a2)) = 2|a1 − f | (4.3)
The resultant distribution of the distance values forms the confocal ellipses with zero
values along the line segment F1F2 (Figure 4.2). So, CED is a valid metric for measuring
the distance from the line segment F1F2 to any point in space.
Definition 22 (Distance from a point to a line segment in terms of CED). The distance
from point P ∈ R2 to line segment l =F1F2 in terms of CED is:
dCED(P, l) = dCED(E(a0), E(aP )) (4.4)
In (4.4), E(aP ) is a unique ellipse passing through P with the focal points F1 and F2.
The length of its semi-major axis is aP . E(a0) is the ellipse degenerated into the line
segment with the focal points F1 and F2, thus, a0 = d2(F1,F2)
2 . In other words, a0 is half
of the length of the line segment connecting the focal points F1 and F2.
Alternatively, dCED(P, l) can be defined by the combination of the Euclidean distances
with regard to (2.5) as follows:
dCED(P, l) = d2(P, F1) + d2(P, F2) − d2(F1, F2) (4.5)
Subtraction of a0 normalizes the distance function by mitigating its dependence on the
line segment length.
4.1.3 Comparison between HD and CED
As can be seen in Figures 4.1 and 4.2, for the line segment, CED and HD produce
different distance value distributions: confocal ellipses and a union of circles, respectively.
To compute a CED distance field it suffices to have two parameters – locations of the
focal points. In contrast, HD takes into account each point of the line segment. If HD
produces the distance field of confocal ellipses, the corresponding representation can
become compact by using CED. Let the HD distance values be propagated from the
ellipse boundary towards the interior. The resultant level sets are compared to the family
of confocal ellipses generated from the focal points of that ellipse.
In Figure 4.3a, the bold green ellipse, E(F1, F2; a), has the foci at F1 and F2. In the
corresponding family of confocal ellipses (solid green), the lengths of major and minor
axes are changing while keeping the distance between the focal points constant. According
to (2.6) and (2.7), it leads to various eccentricity values of confocal ellipses. The HD level
36
4.1. Distance from a Point to a Line Segment
(a) DT2 versus confocal ellipses (b) normals to DT2 level sets (c) normals to confocal ellipses
Figure 4.3: DT2 of the ellipse and the corresponding confocal ellipses
sets propagated from E(F1, F2; a) are elliptic (dashed red in Figure 4.3a). These level sets
have a constant offset with respect to each other, which leads to the constant eccentricity
and a unique pair of focal points for each level set. The smallest distance value increment
follows the direction of the normal to the level set at that point [62]. Following the
normals of the consecutive confocal ellipses forms the hyperbola branches (dashed red in
Figure 4.3c). The normals to the HD level sets form the rays (dashed red in Figure 4.3b).
So, the HD representation of the ellipse cannot be simplified by using CED .
Both HD and CED are extendable to higher dimensions. In 3D, the distribution of
the distance values is obtained by rotation about the line segment F1F2. For HD, the
resultant 3D volume comprises two half-spheres and a cylinder. For CED, it is an ellipsoid
of revolution (Figure 4.4), namely a prolate spheroid, with the median and minor axes
having an equal length. The latter is proven by considering the cross sections passing
through the line segment F1F2. Due to the constant distance sum to two focal points, in
each plane, the generated curve is an ellipse with the same parameters a and b.
Figure 4.4: The example of CED level sets in 3D
37
4. Distance Fields based on the Properties of Generalized Conics
4.2 Confocal Elliptic Field (CEF)
A distance field associates each point in space with its distance to a closest element from
a set of objects [24]. Depending on a metric the level sets vary. When applying the
Euclidean metric, the distance field is referred to as the Euclidean Distance Field (DF2).
In the simplest case, the set of objects contains a point, and the level sets are concentric
circles with the center at that point. Thanks to (2.5) and (2.11), a combination of DF2s
produces the distance fields containing confocal conics.
Definition 23 (Confocal ellipses from two points). Let F = {F1, F2} be the set of two
points. The sum of DF2s generated from F1 and F2 creates a distance field containing
confocal ellipses (Figure 4.5).
Figure 4.5: The distance field containing confocal ellipses
Definition 24 (Confocal hyperbolas from two points). Let F = {F1, F2} be the set of
two points. The difference of DF2s generated from F1 and F2 produces the distance field
containing confocal hyperbolas (Figure 4.6).
Figure 4.6: The distance field containing confocal hyperbolas
Compared to Definition 23, dCED from (4.5) additionally subtracts the line segment
length which, in fact, is present in the distance field.
Property 18 (Distance value that equals the line segment length). The distance value
of F2 in DF2 of F1 equals the length of the line segment F1F2. And vice versa.
Definition 25 (Distance field of a line segment under CED). For the line segment F1F2
the distance field under dCED equals subtraction of the line segment length from the sum
of DF2s generated from F1 and F2 (Figure 4.7). The level sets are confocal ellipses.
38
4.2. Confocal Elliptic Field (CEF)
Figure 4.7: The distance field of the line segment with dCED as a metric
In the special case, when the line segment degenerates into a point (for instance, the
endpoints of F1F2 are identical), the distance field of confocal ellipses degenerates into
the doubled DF2 of this point.
Subtraction of d2(F1, F2) has a normalization effect – the distance values at the points
belonging to F1F2 are zero. Therefore, it is possible to combine multiple distance fields
corresponding to various line segments. Applying the minimum operation to a collection
of such distance fields presents the way to find the distance from a point to a set of line
segments. It implies the notion of Confocal Elliptic Field (CEF).
Definition 26 (Confocal Elliptic Field). Let F= {(F1, F2), (F2, F3), .., (FN , FN+1)} be
the set of line segments. Each point in the Confocal Elliptic Field (CEF) is associated
with the distance value to the closest element in F with respect to CED (refer to (4.5)):
CEF = {P ∈ R2 : inf{dCED(P, li) | li ∈ F , i ∈ [1, ..., N ]}} (4.6)
In other words, in CEF, there is a mapping between each point P ∈ R2 and the smallest
value from the set of distance fields. CEF tessellates the space according to the proximity
of points to the set of line segments.
Definition 27 (Receptive field). Consider F = {(F1, F2), (F2, F3), .., (FN , FN+1)} to be
the set of line segments and CEF generated from it. The set of points that are closer
to the line segment li ∈ F than to any other lj ∈ F , i, j ∈ [1, . . . , N ], j ̸= i defines the
receptive field Ri⊂ R2:
Ri = {P ∈ R2 : CEF(P ) − dCED(P, li) = 0 | li ∈ F , i ∈ [1, ..., N ]} (4.7)
4.2.1 Separating Curve
A set of points in CEF has an identical value in several receptive fields. In other words,
such points are equidistant from at least two elements in the set F .
Definition 28 (Separating curve). A separating curve, denoted as Sij, visually divides
the receptive fields Ri and Rj associated with various objects. It is a zero level set when
taking the difference between these receptive fields:
Sij = {P ∈ R2 : (Ri ∩ Rj = 0) | i, j ∈ [1, . . . , N ]; i ̸= j} (4.8)
39
4. Distance Fields based on the Properties of Generalized Conics
Figure 4.8: CEF of the pair of points. The separating curve is a bisector
The geometric nature of the separating curve depends on the mutual arrangement and
the type of objects in the set F . Here, the object can be a line segment or a point.
Concerning the mutual arrangement, they can intersect or overlap each other, lie on
parallel lines, be at a distance from each other, and connect into a polygon. In this regard,
the separating curve in CEF is either a bisector, a hyperbola branch, or a higher-order
curve. It suffices to demonstrate the types of separating curves on an example of two
objects. When the set F contains more than two elements, the separating curves are
computed for each pair independently and then combined.
Bisector
There are three configurations when the separating curve is a bisector. First, consider
the set F= {F1, F2} containing the pair of points. Each point creates the distance field
of concentric circles (Figure 4.8). Let P ∈ R2be an arbitrary point on the separating
curve, and Q ∈ R2 be the point on the separating curve that belongs to F1F2. From
Definition 28, F1P=F2P= r, as well as F1Q=F2Q. The triangle △F1PF2 has two equal
sides leading to PQ being a bisector [124]. Since this is valid for any P ̸= Q, the resultant
separating curve is the perpendicular bisector to F1F2 (Figure 4.8).
Second, the separating curve is the bisector when the line segments share a common
endpoint and have the same length (Figure 4.9a). Consider the set F= {(F1, F2), (F2, F3)}
and an arbitrary point P ∈R2 belonging to the separating curve. From (4.5):
dCED(P, l1) = d2(P, F1) + d2(P, F2) − d2(F1, F2)
dCED(P, l2) = d2(P, F3) + d2(P, F2) − d2(F2, F3)
(4.9)
Since for the separating curve dCED(P, l1)=dCED(P, l2) and the lengths of the line
segments are the same, d2(F1, F2) = d2(F2, F3), then d2(P, F1) = d2(P, F3). Hence, such
points P form the isosceles triangle △F1PF3, and the resultant separating curve is the
bisector that passes through the common point – F2.
40
4.2. Confocal Elliptic Field (CEF)
(a) (b)
(c) (d)
Figure 4.9: CEF of the pair of line segments. The separating curve is a bisector
Finally, in certain scenarios, the bisector delineates the line segments of the same length
without a common endpoint. They can belong to the same line (Figure 4.9b) or to the
distinct lines, such that the shortest paths between the endpoints (F1F3 and F2F4 in
Figure 4.9c and 4.9d) are parallel to each other and are perpendicular to the midline.
Hyperbola Branch
If two line segments with different lengths share a common endpoint, the separating curve
is a hyperbola branch that passes through this common point (Figure 4.10). Consider the
set F = {(F1, F2), (F2, F3)} and an arbitrary point P ∈R2 that belongs to the separating
curve. According to (4.5):
dCED(P, l1) = d2(P, F1) + d2(P, F2) − d2(F1, F2)
dCED(P, l2) = d2(P, F2) + d2(P, F3) − d2(F2, F3)
(4.10)
41
4. Distance Fields based on the Properties of Generalized Conics
(a) (b)
Figure 4.10: CEF of the pair of line segments. The separating curve is a hyperbola
branch
Equalizing dCED(P, l1) and dCED(P, l2) leads to:
d2(P, F1) − d2(P, F3) = d2(F1, F2) − d2(F2, F3) (4.11)
(4.11) defines the hyperbola branch with the focal points F1 and F3. It passes through
the common point F2, which position influences its curvature (Figure 4.10).
Multifocal Hyperbola Branch
In the remaining cases (Figure 4.11), the separating curve is a multifocal hyperbola
branch (higher-order curve). In Figure 4.11a, the form of separating curve depends on the
mutual arrangement of line segments (for instance, parallel to each other, non-intersecting,
and intersecting) and on their length. The line segment with the greater length has the
greater receptive field in the resultant CEF. In Figure 4.11b, the form of the separating
curve depends on the position of the point relative to the line segment.
4.2.2 Properties of CEF
Depending on the type of objects and their mutual arrangement, CEF is characterized
by specific geometrical properties.
Property 19 (CEF of a point). CEF generated from the point F ∈ R2 contains concentric
circles with the center at F .
Proof. From (4.5) and (4.6), CEF of a single point equals:
CEF = {P ∈ R2 : d2(P, F ) + d2(P, F ) − d2(F, F )} (4.12)
(4.12) defines the doubled DF2 of a point. Thus, CEF contains concentric circles.
42
4.2. Confocal Elliptic Field (CEF)
(a) (b)
Figure 4.11: CEF of (a) the pair of line segments and (b) the point and the line segment.
The separating curve is a multifocal hyperbola branch
Property 20 (CEF of a line segment). CEF of the line segment F1F2 contains confocal
ellipses with the focal points at F1 and F2 ∈ R2.
Proof. According to Definition 25, dCED generates the distance field containing confocal
ellipses. Consequently, CEF of this distance field also contains confocal ellipses.
Property 21 (CEF values at the points of a line segment). The distance values along
the line segment F1F2 equal zero:
CEF((1 − λ)F1 + λF2) = 0, ∀λ ∈ [0, 1] (4.13)
Proof. For each point belonging to the line segment F1F2, the distance sum to the
endpoints equals the length of F1F2. Regarding (4.5), CEF at these points is zero.
Property 22 (CEF of the elements contained in a line segment). CEF of N line segments
and points contained in the line segment F1F2 is CEF generated only from F1F2.
Proof. Consider the pair of line segments F1F2 and F3F4, such that F3F4⊂F1F2 and the
points are ordered as F1, F3, F4, F2. The length of F1F2 is the sum of lengths of the line
segments F1F3, F3F4, and F4F2:
d2(F1, F2) = d2(F1, F3) + d2(F3, F4) + d2(F4, F2) (4.14)
For the proof, it suffices to show that CEF of F1F2 and F3F4 is the distance field generated
by F1F2. By contradiction, from (4.5) and (4.6), for any point P ∈ R2, the following
must be true:
d2(P, F1) + d2(P, F2) − d2(F1, F2) > d2(P, F3) + d2(P, F4) − d2(F3, F4) (4.15)
43
4. Distance Fields based on the Properties of Generalized Conics
According to (4.14), it is possible to simplify (4.15):
d2(P, F1) + d2(P, F2) − d2(F1, F3) − d2(F4, F2) > d2(P, F3) + d2(P, F4) (4.16)
First, let the point P be a part of F1F2. According to Property 21, in the distance field
of F1F2, all the points belonging to this line segment have zero distance values. In the
distance field of F3F4, the distance values along F3F4 are zero, and the distance values
along F1F3 and F4F2 are greater than zero. Thus, there is a contradiction in (4.15).
Second, let the point P be to the left of F1 on the line containing F1F2. Therefore,
d2(P, F3) − d2(P, F1) = d2(F1, F3) and d2(P, F2) − d2(P, F4) = d2(F4, F2), resulting
in (4.16) becoming
−d2(F1, F3) + d2(F4, F2) > d2(F1, F3) + d2(F4, F2) (4.17)
(4.17) and, consequently, (4.15) are false. Contradiction. If the point P is to the right of
F2 and is on the line containing F1F2, then the reasoning is similar.
Third, let the point P be not on the line segment F1F2. Permutation in (4.16) leads to:
d2(P, F1) − d2(P, F3) + d2(P, F2) − d2(P, F4) > d2(F1, F3) + d2(F4, F2) (4.18)
According to the triangle inequality [34],
d2(F1, F3) ≥ | d2(P, F1) − d2(P, F3)| (4.19)
d2(F4, F2) ≥ | d2(P, F2) − d2(P, F4)| (4.20)
Hence, (4.18) and, consequently, (4.15) does not hold. Contradiction.
Similarly, it can be shown that CEF of the line segment F1F2 and the point F5 ⊂F1F2 is
the distance field of F1F2.
4.3 Confocal Multifocal Elliptic and Hyperbolic
Fields (CMEF and CMHF)
With the reference to Definitions 15 to 17, the distance fields containing confocal multifocal
ellipses and hyperbolas can be computed as a combination of multiple DF2s.
Definition 29 (Confocal Multifocal Elliptic Field). Let F = {F1, F2, . . . , FN } be the set
of N points with the positive weights w1, w2, . . . , wN . The sum of weighted DF2s generated
from F1, F2, . . . , FN produces the distance field of confocal multifocal ellipses (Figure 4.12),
called Confocal Multifocal Elliptic Field (CMEF).
The example is illustrated in Figure 4.12. The DF2s are generated from the triplet of
points F1, F2, and F3. Then, each point in these fields is multiplied by the corresponding
weight, w1, w2, or w3. Finally, CMEF is computed by assigning to each point the sum
of its values in the weighted distance fields.
44
4.4. Summary
Figure 4.12: CMEF computed for the triplet of points with the corresponding weights
w1 = 0.3, w2 = 0.5, and w3 = 0.5
Definition 30 (Confocal Multifocal Hyperbolic Field). Consider two sets of focal points
F = {F1, F2, . . . , FN } and G = {G1, G2, . . . , GM } with the positive weights w1, w2, . . . , wN
and ν1, ν2, . . . , νM respectively. The subtraction from the sum of weighted DF2s generated
from F the sum of weighted DF2s generated from G produces the distance field of confocal
multifocal hyperbolas (Figure 4.13), called Confocal Multifocal Hyperbolic Field (CMHF).
Figure 4.13: CMHF from the two sets of points F = {F1, F2} and G = {G1} with the
corresponding weights w1 = 0.7, w2 = 0.5, and ν1 = 0.3
The example in Figure 4.13 considers two point sets, F = {F1, F2} and G = {G1}. First,
DF2s are computed for all points F1, F2, and G1 and multiplied by the corresponding
weight w1 = 0.7, w2 = 0.5, and ν1 = 0.3. Then, for each point in space, the distance values
from DF2s associated with the set F are added, whereas with the set G – subtracted.
4.4 Summary
This chapter illustrates how the identified geometrical properties of conics and generalized
conics are applied to shape representation. In relation to the distance fields, the essence
of the multifocal ellipses is to define the proximity to the objects, whereas the multifocal
hyperbolas establish the tessellation of the space. A distinct feature of CEF is the impact
mitigation for the elements contained inside a line segment (Property 22). Despite the
number of elements, there will be no corresponding separating curve indicating their
presence. An interpretation of the proposed distance fields by a combination of DF2s
enables an efficient representation. It suffices to have a set of focal points and the
corresponding weights to generate the representation.
45

CHAPTER 5
Generating CEF, CMEF, and
CMHF with Distance Transform
This chapter is based on the following publications:
Aysylu Gabdulkhakova, Walter G. Kropatsch:
Confocal Ellipse-based Distance and Confocal Elliptical Field for polygonal shapes. In
Proceedings of the International Conference on Pattern Recognition, pages 3025–3030,
2018 [56]
Aysylu Gabdulkhakova, Maximilian Langer, Bernhard W. Langer, Walter G. Kropatsch:
Line Voronoi Diagrams Using Elliptical Distances. In Proceedings of the Joint IAPR
International Workshop on Structural, Syntactic, and Statistical Pattern Recognition,
pages 258–267, 2018 [59]
Aysylu Gabdulkhakova, Walter G. Kropatsch:
Generalized conics: properties and applications. In Proceedings of the International
Conference on Pattern Recognition, pages 10728–10735, 2020 [57]
Digital geometry deals with N -dimensional digital spaces and is referred to as the
geometry of the computer screen [77]. It adapts the fundamental concepts of Euclidean
geometry to the discrete case while considering a sampling of the Euclidean space. The
transformation of a continuous function into a discrete form that can be processed by a
computer is called digitization [79]. In 2D space, the result consists of pixels (Figure 5.1a).
It creates a finite data structure defining a regular orthogonal grid. The shape digitization
is performed at the cost of accuracy. For example, a line segment becomes a finite set of
tiles [31], which is still perceived as a connected line segment by human (Figure 5.1b).
The key principle of digital geometry is to take a notion in Euclidean geometry and see if
it remains valid in its digital interpretation [77]. According to this principle, the present
47
5. Generating CEF, CMEF, and CMHF with Distance Transform
chapter aims at analysing the Confocal Elliptic Field (CEF), Confocal Multifocal Elliptic
Field (CMEF), and Confocal Multifocal Hyperbolic Field (CMHF) in the digital space.
(a) pixel (white) (b) digitized line segment (green)
Figure 5.1: The objects in the digital space
5.1 Preliminaries
While switching to the digital space, it is necessary to provide alternative definitions of
the notions defined for the Euclidean space (Chapter 2). Here, the space is transformed
to a digital image, whereas a point - to a pixel.
Definition 31 (2D digital image). A 2D digital image, I2, is a function defined on a
finite regular orthogonal subset of Z2
≥0 as follows:
I2 : Z2
≥0 → RN , (5.1)
where Z2
≥0 corresponds to the coordinate set, and RN - to the value set.
Definition 32 (Pixel). The smallest unit of a 2D digital image is called pixel. It is
characterized by a pair of integer coordinates and a value. The value can be expressed by
a single integer (for example, a binary image) or by a vector of integers (for example, an
RGB image).
In principle, a 2D digital image is a discrete set of pixels. In the computer vision domain,
a binary image contains two types of pixels: (1) feature (foreground) elements - pixels
having a value 1, (2) non-feature (background) elements - pixels having a value 0 [157].
In image processing, the distance between two pixels reflects spatial information (for
example, the distance from the non-feature element to the closest feature element) [26]
or characteristic information (for instance, the probability that the non-feature element
belongs to the set of feature elements) [94]. This thesis focuses on spatial information.
Such a spatial distance relies on the type of pixel connectivity and the metric. The
connectivity type influences the distance value propagation towards the other pixels
in an image. On a 2D grid, 4-connectivity considers the adjacent pixels to be in the
48
5.2. Distance Transform (DT)
(a) 4-connectivity (b) 8-connectivity (c) City-Block (d) Chessboard
Figure 5.2: The distance value propagation depending on the connectivity type
horizontal and vertical directions (Figure 5.2a). In the case of 8-connectivity, the pixel
additionally has neighbors in the diagonal direction (Figure 5.2b). The examples of 4- and
8-connectivity-based distance value propagations are used in the City-Block (Figure 5.2c)
and Chessboard (Figure 5.2d) metrics, respectively [26].
5.2 Distance Transform (DT)
Chapter 4 introduced the distance fields based on the properties of conics and generalized
conics. In order to compute such fields in the discrete space efficiently, it is proposed to
apply the classical image processing approach called Distance Transform (DT) [26].
Definition 33 (Distance Transform). Consider a 2D binary image I2
binary and the set of
feature elements F , where I2
binary(F ) = 0, ∀F ∈ F . The Distance Transform (DT) is
an operator that assigns to each pixel in I2
binary the distance value to the nearest feature
element with regard to the selected metric (d):
DF = {P ∈ I2
binary : min{d(P, F )|F ∈ F}} (5.2)
As follows from the definition, the selected metric highly influences the properties of the
resultant distance field. In the computer vision community, the Euclidean distance plays
a crucial role since providing invariance under rotation, translation, and bending in 2D
but not under scaling [127].
In principle, DT is a global operation which is computationally expensive [26]. A
direct implementation of the Euclidean Distance Transform (DT2) has a complexity
of O(N4) [162]. Thus, the early approaches aimed at efficient solutions at the cost
of approximating the Euclidean distance [136, 137]. Maurer et al. [96] introduce the
algorithm to compute the exact DT2 in linear time. Ciesielski et al. [37] further improve
this method. Various authors approach DT2 in 3D space [27,117].
DT is successfully applied in a wide variety of applications, such as image segmentation,
object recognition, image matching, skeletonization, and shape analysis [37]. Concerning
shape analysis, the distances are propagated from the interior of shape to its borders.
Hence, to capture the shape structure, it is preferred to use the inverse DT by taking the
49
5. Generating CEF, CMEF, and CMHF with Distance Transform
complement of the binary image [140]. Meyer et al. [102] takes the discontinuities in the
inverse DT2 values to detect the boundaries of distinct overlapping objects. When applied
to the problem of overlapping elliptic shapes, Talbot et al. [171] introduce Elliptical
Distance Transform (LDT). Here, the Euclidean distance is substituted by the standard
2D harmonic oscillator equation. The optimization of the LDT series with various
eccentricity and orientation parameters enables detecting the minimal set of maximal
ellipses that cover the shape. The distance values are computed for the pairs of points.
The next section introduces the DT-based method to generate CEF, CMEF, and CMHF.
5.3 CEF in Discrete Space
DT makes it possible to adapt the continuous notions into discrete space. In this regard,
consider the interpretations of Definitions 23 to 28.
Definition 34 (Confocal ellipses from two pixels with DT2). Let F = {F1, F2} be the
pair of pixels in a 2D binary image I2
binary. Confocal ellipses in the discrete space are the
sum of DT2s generated from F1 and F2:
DEF1F2 = {P ∈ I2
binary : DF1(P ) + DF2(P )} (5.3)
Strand [166] presented the idea of taking the sum of distance fields. It aimed at finding a
minimal path between two pixels. Though, the resultant distance field was not analyzed
and used from the geometrical perspective of confocal ellipses.
Definition 35 (Confocal hyperbolas from two pixels with DT2). Let F = {F1, F2} be
the pair of pixels in a 2D binary image I2
binary. Confocal hyperbolas in discrete space are
obtained as the difference of the DT2s generated from F1 and F2:
DHF1F2 = {P ∈ I2
binary : DF1(P ) − DF2(P )} (5.4)
Property 23 (Distance value that equals the line segment length in DT2). Let DF1(P )
and DF2(P ) be DT2s of the pixels from the set F= {F1, F2}. The distance value of the
pixel that was not used to generate DT2 equals the length of F1F2:
DF1(F2) = DF2(F1) = d2(F1, F2) (5.5)
Definition 36 (Distance field of a line segment under CED with DT2). Consider the
line segment defined by two endpoints F= {F1, F2}. The distance field of confocal ellipses
with respect to CED using DT2 is then expressed as DEF1F2:
DEF1F2 = {P ∈ I2
binary : DEF1F2(P ) − DEF1F2(F1) = (5.6)
= DEF1F2(P ) − DEF1F2(F2) = (5.7)
= DF1(P ) + DF2(P ) − DF1(F2) = (5.8)
= DF1(P ) + DF2(P ) − DF2(F1)} (5.9)
50
5.3. CEF in Discrete Space
The substantial difference between DEF1F2 and DEF1F2 is the subtraction of the F1F2
length. In DEF1F2 , the distance value of its pixels is normalized and is independent from
the distance between F1 and F2. So it is possible to combine multiple distance fields by,
for example, applying the minimum operation to each pixel.
Definition 37 (Confocal Elliptic Field in terms of DT2). Given the set of line segments,
F= {(F1, F2), ..., (FN−1, FN )}, the Confocal Elliptic Field in terms of DT2 (CEFDT2)
is obtained by the pixel-wise minimum operation that is applied to the distance fields
DEF1F2,..., DEFN−1FN
:
CEFDT2(P ) = {P ∈ I2
binary : min{DEFi−1Fi(P )| i = [2, . . . , N ]}} (5.10)
Property 24 (CEFDT2 values at the pixels of a line segment). Let DEF1F2 be the distance
field from the set F= {(F1, F2)}. The distance values of the pixels belonging to the discrete
line segment F1F2 are less than or equal to the threshold τ :
DEF1F2((1 − λ)F1 + λF2) ≤ τ <
√
2 pixel_edge_length, ∀λ ∈ [0, 1] (5.11)
As opposed to the continuous case, the space discretization leads to an accuracy problem.
The maximum DT2 error within the pixel equals
√
2
2 pixel_edge_length [83]. In the
extreme case, this distance expresses the semi-major axis of the ellipse, forming the
right triangle with the side lengths a, b, and f . According to the triangle inequality [34],
(a − f) ≤ b, thus, (a − f) <
√
2
2 pixel_edge_length. The distance value associated with
each pixel in DEF1F2 equals 2(a − f). So, using the threshold τ<
√
2 pixel_edge_length
enables handling the numerical error.
Definition 38 (Receptive field in terms of DT2). Consider CEFDT2 generated from
the set F containing N line segments. The receptive field DRi ∈ I2
binary of the i-th line
segment, li, is the set of pixels, where the absolute difference between CEFDT2 and DE li
is less than or equal to the threshold τ :
DRi = {P ∈ I2
binary : |CEFDT2(P ) − DE li(P )| ≤ τ | li ∈ F , i ∈ [1, . . . , N ]} (5.12)
In the discrete space, the definition of separating curve (discussed in Section 4.2.1)
remains the same under the condition that threshold τ is accounted.
Definition 39 (Separating curve in terms of DT2). Consider the pair of receptive fields
DRi and DRj, DRi ̸= DRj. The separating curve, DSij, is the set of pixels where the
absolute difference between these receptive fields is less than or equal to the threshold τ :
DSij = {P ∈ I2
binary : (|DRi(P ) − DRj(P )| ≤ τ) | i, j ∈ [1, . . . , N ]; i ̸= j} (5.13)
51
5. Generating CEF, CMEF, and CMHF with Distance Transform
5.4 CMEF and CMHF in Discrete Space
Analogically to CEF, the continuous notions of CMEF and CMHF are revisited. This
section redefines the above concepts in the digital space with the use of DT.
Definition 40 (Confocal Multifocal Elliptic Field in terms of DT2). Consider the set of
points, F= {F1, F2, ..., FN }, and the corresponding DT2s containing concentric circles,
DF1 , DF2 ,. . . , DFN
. Each distance field is multiplied by the corresponding positive weight
w1, w2, . . . , wN . The Confocal Multifocal Elliptic Field in terms of DT2 (CMEFDT2) is
computed as a pixel-wise sum among all the weighted distance fields:
CMEFDT2 = {P ∈ I2
binary :
N
i=1
wiDFi(P ) | i = [1, . . . , N ]} (5.14)
Definition 41 (Confocal Multifocal Hyperbolic Field in terms of DT2). Consider the
two sets, F= {F1, F2, ..., FN } and G= {G1, G2, ..., GM }. DF1, DF2,. . . , DFN
, computed
from the elements in F , are linked to the positive weights w1, w2, . . . , wN , whereas
DG1 , DG2 ,. . . , DGM
, generated from G elements are associated with the positive weights
ν1, ν2, . . . , νM . The Confocal Multifocal Hyperbolic Field in terms of DT2 (CMHFDT2)
equals the pixel-wise difference between the sums of weighted distance fields:
CMHFDT2 = {P ∈ I2
binary :
N
i=1
wiDFi(P ) −
M
j=1
νjDGj (P ) | i = [1, . . . , N ],
j = [1, . . . , M ]}
(5.15)
5.5 CEFDT under the Various Metrics
According to Definition 36, CEFDT2 relies on the Euclidean distance. In principle, it
is possible to use other metrics. This section illustrates and compares the results of
applying the grid-based metrics such as the City-Block and Chessboard distances.
The City-Block distance (also referred to as Manhattan, rectilinear distance, or L1-metric)
in 2D considers the 4-connectivity distance value propagation. In other words, it measures
the route length between two points along the regular grid at the right angles [82].
Definition 42 (City-Block distance). Given the pixels P = (xP , yP ) and Q = (xQ, yQ),
the City-Block distance equals the sum of absolute differences of their corresponding
coordinates:
d1(P, Q) = |xP − xQ| + |yP − yQ| (5.16)
The Chessboard distance (alternatively Chebyshev distance, or L∞-metric) in 2D considers
the 8-connectivity distance value propagation and is the rotated and scaled equivalent of
the planar City-Block distance [135].
52
5.5. CEFDT under the Various Metrics
(a) Euclidean (DT2) (b) City-Block (DT1) (c) Chessboard (DT∞)
Figure 5.3: The distance fields of the single point using the various metrics
Definition 43 (Chessboard distance). The Chessboard distance between the pixels
P = (xP , yP ) and Q = (xQ, yQ) equals the maximum of absolute differences of their
corresponding coordinates:
d∞(P, Q) = max(|xP − xQ|, |yP − yQ|) (5.17)
The relation between the metrics is illustrated as follows. Let the two points, P = (xP , yP )
and Q = (xQ, yQ), form the hypotenuse of the right triangle. The Euclidean distance
equals the length of the hypotenuse, the Chessboard distance matches the length of the
longest cathetus, and the City-Block distance is the sum of the catheti lengths.
For a single pixel, the DT2 level sets are concentric circles (Figure 5.3a). In contrast, the
City-Block Distance Transform (DT1) and the Chessboard Distance Transform (DT∞)
form rhombic and square level sets (Figure 5.3b and 5.3c respectively).
Now, compare the distance fields for the line segment (Figure 5.4 and 5.5). DT2, DT1,
and DT∞ compute for any pixel P the distance to the closest pixel belonging to F1F2 with
regard to the selected metric (Figure 5.4). CEFDT is based on (4.5). Substitution of the
Euclidean metric by the City-Block or Chessboard produces the distance fields which level
sets differ from confocal ellipses (Figure 5.5). From the computer vision perspective, the
Euclidean distance provides the invariance to translation and rotation [127]. In contrast,
the Chessboard and City-Block distances depend on the rotation of the coordinate system
but are invariant to translation [27,82]. Consequently, this is reflected in CEFDT. Observe
the Euclidean (Figure 5.4a, 5.4d, 5.5a and 5.5d), City-Block (Figure 5.4b, 5.4e, 5.5b
and 5.5e) and Chessboard (Figure 5.4c, 5.4f, 5.5c and 5.5f) distance fields.
Without loss of generality, DT and CEFDT fields of a line segment, generated using the
Chessboard and City-Block metrics, differ from each other. The following properties
characterize the two exceptions. Here, CEFDT optimizes the computational efficiency
while considering only the pair of endpoints regardless of the line segment discretization.
Property 25 (Similarity between DT1 and CEFDT1). DT1 and CEFDT1 generate
identical level sets if the line segment is parallel to one of the axes (Figure 5.4b and 5.5b).
The difference is in the distance values: CEFDT1 is twice as large as DT1.
53
5. Generating CEF, CMEF, and CMHF with Distance Transform
(a) Euclidean (DT2) (b) City-Block (DT1) (c) Chessboard (DT∞)
(d) Euclidean (DT2) (e) City-Block (DT1) (f) Chessboard (DT∞)
Figure 5.4: DT of a line segment using the various metrics
(a) Euclidean (CEFDT2) (b) City-Block (CEFDT1) (c) Chessboard (CEFDT∞)
(d) Euclidean (CEFDT2) (e) City-Block (CEFDT1) (f) Chessboard (CEFDT∞)
Figure 5.5: CEFDT of a line segment using the various metrics
54
5.5. CEFDT under the Various Metrics
Figure 5.6: The characteristic pixels P1, P2, P3, and P4 of a single λ level set
Proof. Assume λ and r denote the distance values of the corresponding level sets of DT1
and CEFDT1 (Figure 5.6). It suffices to show that λ = 2r for four characteristic pixels:
P1, P2, P3, and P4. Let an arbitrary pixel P correspond to the λ level set of the CEFDT1 .
Assume that F1 and F2 are the focal points. Substitute the Euclidean distance in (4.5):
λ = dCED(P, F1F2) = d1(P, F1) + d1(P, F2) − d1(F1, F2) (5.18)
The right side of (5.18) can be rewritten as follows:
(|xP − xF1 | + |yP − yF1 |) + (|xP − xF2 | + |yP − yF2 |) − (|xF1 − xF2 | + |yF1 − yF2 |) (5.19)
In the case of P = P1, the y-coordinates are identical for P1, F1, and F2, whereas the
x-coordinates are related as xP1 ≤ xF1 ≤ xF2 . Thus, (5.19) becomes:
xF1 −xP1 +yP1 −yF1 +xF2 −xP1 +yP1 −yF2 −xF2 +xF1 +yF1 −yF2 = 2(xF1 −xP1) (5.20)
At the same time DT1-value of P1 equals (xF1 − xP1) and, thus:
λ = 2d1(P1, F1) = 2r (5.21)
Similarly, it can be shown that (5.21) is valid for P2, P3, and P4.
Property 25 does not hold true when the line segment is not parallel to any of the
axes (Figure 5.4e and 5.5e). It can be proven by comparing CEFDT1 and DT1 values for
all possible relations between x- and y-coordinates of an arbitrary point P and the line
segment F1F2.
Property 26 (Similarity between DT∞ and CEFDT∞). DT∞ and CEFDT∞ generate
identical level sets if the line segment is rotated by 45◦, 135◦, 225◦, or 315◦ about one of
the axes (Figure 5.4f and 5.5f). The difference is in the distance values: CEFDT∞ is
twice as large as DT∞.
Proof. According to Definition 43, the DT∞ level sets of a single point are concentric
squares (Figure 5.3c). In Figure 5.7, consider the level sets with the centers at F1, F2,
and FP passing through P and the level set containing F1 with the center at F2. Here,
55
5. Generating CEF, CMEF, and CMHF with Distance Transform
Figure 5.7: Computing the CEFDT∞ and DT∞ values of the line segment rotated by 45◦
the point FP denotes the closest point to P in terms of the Chessboard distance. In
DT∞, the distance value of P equals half of the side length of the smallest square which
center is on F1F2. Such a square has a center at FP and the length of its side equals 2l.
Consequently, the DT∞ value of P is l.
Assume λ denotes the CEFDT∞ value of P . According to (4.5) it equals:
λ = dCED(P, F1F2) = d∞(P, F1) + d∞(P, F2) − d∞(F1, F2) (5.22)
Express d∞(P, F1) and d∞(P, F2) using l (Figure 5.7):
d∞(P, F1) = l + n
d∞(P, F2) = l + m
(5.23)
Since the line segment F1F2 is rotated by 45◦, the sides of the right triangles with a
hypotenuse along F1F2 are equal:
d∞(F1, F2) = m + n (5.24)
After substituting the estimates from (5.23) and (5.24) to (5.22):
λ = l + n + l + m − (m + n) = 2l (5.25)
From (5.25), the value of P in CEFDT∞ is twice as large as its DT∞ value.
56
5.6. Discussion
5.6 Discussion
In this section, CEFDT, CMEFDT, and CMHFDT are evaluated according to the proposed
evaluation criteria. The results are summarized in Table 5.1.
CEFDT CMEFDT CMHFDT
Scope any 2D set of points and
line segments
focal points can be points, line segments,
or shapes
extension to higher dimensions
Uniqueness unique for the set of focal points (with weights)
Invariance •Euclidean: invariant to rotation, translation, and scaling
•City-Block: invariant to translation, and scaling
•Chessboard: invariant to translation, and scaling
Stability
stable in the cases
satisfying Property 22
every point affects the representation
global minimum is
less affected by
distant outliers
Accuracy •Euclidean:
3
√
2
2 pixel_edge_length N
√
2
2 pixel_edge_length
•City-Block:
3 pixel_edge_length N pixel_edge_length
•Chessboard:
3
2pixel_edge_length N
2 pixel_edge_length
Efficiency •Sequential (Euclidean):
O(N × W × H) [83] O(W × H)
•Parallel (Euclidean):
O(N) [83] O(1)
Abstraction enables hierarchical representation
Table 5.1: Evaluation of the representations CEFDT, CMEFDT, and CMHFDT
Scope
By Definition 22, CED measures the distance between a point and a line segment. So, it
is applicable to sets of line segments which, in fact, can degenerate into points. CEFDT2
relies on CED as a metric and is a combination of DT2s. In turn, DT2 is defined
everywhere in space. Hence, CEFDT2 represents space tessellation of any 2D set of
points and line segments. With the reference to Section 4.1.3, CED enables extension
of the representation to higher dimensions by considering more coordinates. Figure 5.8
57
5. Generating CEF, CMEF, and CMHF with Distance Transform
Figure 5.8: The isosurfaces of CEFDT2 generated from two line segments
shows the 3D representation of CEFDT2 from two line segments, F1F2 and F2F3. The
corresponding isosurfaces are a fusion of prolate spheroids (orange), each obtained by
a rotation of the ellipse about its major axis. Since the line segments have a common
endpoint, the spheroids are separated by the hyperbolic surface (blue).
CMEFDT2 and CMHFDT2 are sums and differences of weighted distance fields, expressing
the distances to the set of focal points. In principle, the focal point is not limited to a
point or a line segment and could be even a shape. Consequently, the distance fields could
be of various types. For instance, consider the set of line segments where the distance
field of each element is expressed by CEFDT2 . The corresponding CMEFDT2 becomes the
pixel-wise sum of multiple CEFDT2s. Eventually, these representations are not limited
to a specific class of shapes and can be extended to higher dimensions. The statements
remain valid for other metrics (for example, City-Block or Chessboard) as well.
Uniqueness
According to Theorem 4, CED is a metric. With the reference to Definition 7, each pixel
is associated with a unique non-negative number. For the given shape there exist a unique
CEFDT2 . At the same time, each pixel in CMEFDT2 is associated with a weighted sum of
unique distance fields. Hence, this representation is also unique. Eventually, CMHFDT2
unambiguously expresses the distance value distribution for the pair of CMEFDT2-fields.
The same holds when substituting the Euclidean distance with City-Block or Chessboard.
Invariance
Depending on the distance metric, the invariance to transformations differs. CEFDT2 ,
CMEFDT2 , and CMHFDT2 are a combination of multiple DT2s, which, in turn, are
invariant under rotation and translation [127]. Substitution of the Euclidean distance
58
5.6. Discussion
by City-Block or Chessboard limits the invariance possibilities to translation [27, 82]. A
normalization strategy enables achieving scale invariance for the discussed metrics [120].
Stability
Essentially, CEFDT is a form of DT that uses CED instead of the Euclidean metric. DT
is sensitive even to a single noise-point [113]. So is the CEFDT. Although, there is an
exception. This effect is mitigated according to Property 22. The distance field only
reflects the values of the line segment that completely encloses other feature elements.
In CMEFDT, every point is mapped to the sum of the distances to the focal points. Thus,
the distance field is stable, if the new focal point is equidistant to all points in space.
This is impossible. CMHFDT is a difference between a pair of CMEFDT. Hence, every
element in the set of focal points impacts these representations.
When considering CMEFDT, every element influences the level sets. Although, if there
is a collection of spatially close elements, the distant outlier does not affect much the
location of the global minimum. Imagine this configuration from far away: the collection
of shapes degenerates into a super-point while the outlier stays as it is. The distance to
the super-point equals the sum of the distances to its elements. Eventually, it can be
encoded as an egg-shape, where the largest weight is associated with the super-point.
According to Theorem 1, for the egg-shape the focal point with the larger weight is
mapped to the minimum distance value. In this case, in the area of the super-point.
Accuracy
Space discretization leads to an accuracy problem: all points within the pixel have the
same distance value related to its center. When considering the Euclidean distance,
the maximum error is at the pixel corners and equals
√
2
2 pixel_edge_length (half of
the pixel diagonal) [83]. For the City-Block and Chessboard distances such error is
pixel_edge_length and 1
2 pixel_edge_length correspondingly.
CED implies using the distance field three times (Definition 36). Thus, the maximum
error in CEFDT2 equals 3
√
2
2 pixel_edge_length, in CEFDT1 3 pixel_edge_length, and
in CEFDT∞
3
2 pixel_edge_length.
CMEFDT and CMHFDT consider the sum (and subtraction) of N distance fields. It results
in the total error of N
√
2
2 pixel_edge_length for the Euclidean, N pixel_edge_length
for the City-Block, and N
2 pixel_edge_length for the Chessboard distance.
Efficiency
The pseudocode of CEFDT2 implementation is shown in Algorithm 5.1. The input
contains the binary image, I2
binary of size W × H, and the set of M pairs of N points,
F . The first step (Lines 1-3) computes DT2s of the points. Since DT2 is linear with
regard to the number of pixels [96], the complexity of the step is O(N × W × H). The
59
5. Generating CEF, CMEF, and CMHF with Distance Transform
next loop (Lines 4-7) aims at computing the distance fields of confocal ellipses. Taking
the pixel-wise sums for pairs of DT2s has the complexity of O(M × W × H). The final
step (Lines 8-15) computes CEFDT2 as the pixel-wise minimum operation among M
distance fields with the complexity of O(M × W × H). If all the steps are performed
sequentially, then the total worst-case complexity of the algorithm is O(N × W × H).
Algorithm 5.1: Confocal Elliptic Field using DT (CEFDT2)
Data: Input binary image I2
binary of size W × H; set F containing M pairs of N
points
Result: Confocal Elliptic Field in terms of DT2 (CEFDT2)
1 for n ← 1 to N do
2 DFn←− compute_DT2(Fn);
3 end
4 foreach fm ∈F , m ∈ [1, . . . , M ] do
5 (Fi, Fj) ←− get_feature_elements(fm);
6 DEm ←− DFi + DFj − DFi(Fj);
7 end
8 foreach [w, h] ∈ W × H do
9 CEFDT2 [w, h] ←− ∞;
10 end
11 foreach [w, h] ∈ W × H do
12 for m ← 1 to M do
13 CEFDT2 [w, h] ←− min(DEm[w, h],CEFDT2 [w, h]);
14 end
15 end
Each step has a potential for parallel execution. The computation of DT2s and the
confocal ellipses can be distributed with respect to the points and line segments, whereas
the pixel-wise minimum operation – with respect to each pixel. This leads to the total
parallel complexity of O(W × H). Langer [83] proposed the alternative algorithm for
DT2 (Lines 1-3). It takes a precomputed DT2 of a point at the center. This DT2 is twice
as large as the input binary image. Instead of computing DT2 for each point, it needs
only to sample the corresponding part of the precomputed distance field. Hence, the
actual parallel complexity depends only on the number of points, O(N).
Algorithm 5.2 describes the computation of separating curves. It follows Algorithm 5.1,
hence, the set of distance fields of confocal ellipses (DE1, . . . ,DEM ) and CEFDT2 are
provided as an input. The proposed steps find the separating curve according to
Definition 39. The similar approach is described in [74]. First (Line 1-3), the receptive
fields are computed as the difference between CEFDT2 and the distance fields of confocal
ellipses. If the difference in distance values is less than or equal to the threshold τ , then
the pixel belongs to the receptive field. The complexity of this step equals O(M ×W ×H),
where M is the number of the receptive fields, W × H is the total number of pixels in
60
5.6. Discussion
an image. The next step (Line 4-10), computes the separating curves by finding the
common pixels of multiple receptive fields. The complexity of this step, as well as total
complexity of the algorithm, is O(M2 × W × H). Algorithm 5.2 can be implemented in
a distributed manner, thus, simplifying the total complexity to O(M2).
Langer [83] proposed the efficient solution that maps pixels of receptive fields with labels.
Each label uniquely represents the element in the set F . The neighboring pixels with
different labels are part of the separating curve. In this case, the parallel computational
complexity equals O(M), although the skeleton is not one-pixel thick.
Algorithm 5.2: Separating Curves
Data: Confocal Elliptic Field in terms of DT2 (CEFDT2); M distance maps of
confocal ellipses DE1,. . . ,DEM ; threshold τ
Result: Separating curves DS
1 for m ← 1 to M do
2 DRm←−| CEFDT2−DEm |≤τ ;
3 end
4 for l ← 1 to M do
5 for k ← 1 to M do
6 if l ̸= k then
7 DS lk ←− | DRl− DRk |≤τ ;
8 end
9 end
10 end
Algorithm 5.3: Confocal Multifocal Elliptic Field in terms of DT2 (CMEFDT2)
Data: Set F containing N points; weights w1, w2, . . . , wN
Result: Confocal Multifocal Elliptic Field in terms of DT2 (CMEFDT2)
1 for n ← 1 to N do
2 DFn←− compute_DT2(Fn);
3 end
4 CMEFDT2←− 0;
5 for n ← 1 to N do
6 CMEFDT2 ←− CMEFDT2 + wnDFn ;
7 end
Algorithm 5.3 shows the computation of CMEFDT2 . As an input it takes the set of N
points. The whole process considers the pixel-wise sums among all the distance fields
DF1 ,. . . , DFN
multiplied by the respective weight. Hence, the total sequential complexity
equals O(N × W × H), where W × H is the number of pixels in an image. Computation
of CMEFDT2 can be implemented in a distributed manner on the pixel level using the
precomputed distance fields. This leads to the actual parallel complexity of O(N).
61
5. Generating CEF, CMEF, and CMHF with Distance Transform
Eventually, the pseudocode for CMHFDT2 is given in Algorithm 5.4. It has the linear
computational complexity on the number of image pixels.
Algorithm 5.4: Confocal Multifocal Hyperbolic Field in terms of DT2
(CMHFDT2)
Data: A pair of distance fields containing multifocal ellipses CMEFDT2
′ and
CMEFDT2
′′
Result: Confocal Multifocal Hyperbolic Field in terms of DT2 (CMHFDT2)
1 CMHFDT2←− CMEFDT2
′ - CMEFDT2
′′;
Abstraction
Similar to the work of Rosin et al. [138], scale-space CEFDT2 is achievable by considering
various levels of object’s discretization. On the other hand, hierarchical representation of
CEFDT2 can be created by thresholding the significance of the line segments and points.
5.7 Summary
The fact that CEF, CMEF, and CMHF are composed of DF2s, enables expressing them
with DT in discrete space. The corresponding parallel algorithms achieve a linear time
complexity for CEFDT2 and CMEFDT2 , and a constant time complexity for CMHFDT2 .
As opposed to the continuous case, this technique requires a threshold to cope with
numerical instabilities and discretization artefacts. Despite sensitivity of CMEFDT level
sets to every point, the position of the global minimum in this field is less affected even by
the distant outliers. Substitution of the Euclidean metric by City-Block and Chessboard
results in losing the rotation invariance. In exceptional cases CEFDT1 and CEFDT∞ are
identical to the classical distance fields. Consequently, in the corresponding scenarios,
DT1 and DT∞ can be computed efficiently by applying the CEFDT algorithm.
62
CHAPTER 6
Elliptic Line Voronoi Diagram
This chapter is based on the following publication:
Aysylu Gabdulkhakova, Maximilian Langer, Bernhard W. Langer, Walter G. Kropatsch:
Line Voronoi Diagrams Using Elliptical Distances. In Proceedings of the Joint IAPR
International Workshop on Structural, Syntactic, and Statistical Pattern Recognition,
pages 258–267, 2018 [59]
Chapters 4 and 5 discussed the distance field computation using CED as a metric in
continuous and discrete spaces, respectively. While reflecting the proximity to the objects
in the target set, the space tessellation in the distance field is, in principle, a mapping of
the Voronoi regions onto a digital grid [114].
The Voronoi Diagram (VD), or the Dirichlet Tessellation, is the fundamental concept
used in various disciplines [12]. The mathematicians Dirichlet [46] and Voronoy [178]
introduced the original concept formally, whereas Shamos and Hoey [153] presented it
in the field of computational geometry. This geometrical construct is applied in a vast
variety of applications [168], such as motion planning [23,55], skeletonization [114,115],
point-location [49], clustering [149], segmentation [76], and finite element analysis [154].
VD is a data structure that provides a space tessellation into cells based on proximity to
the given set of objects, called sites. Each point in space is associated with a closest site
among the set. The points corresponding to the same site form the cell. The notion of
proximity is interpreted from two perspectives. On one side, it is a metric that defines
a distance between objects. The properties and application areas of different metrics
in 2D are thoroughly discussed in the literature [11]: City-Block [68], Euclidean [47],
Lp [85], convex distance functions [35], convex polygon-offset distance function [18],
crystal growth [147], skew distance [3], and power distance [9]. Klein et al. [78] introduce
the analysis of metric classes and their impact on the VD properties.
63
6. Elliptic Line Voronoi Diagram (ELVD)
On the other side, the proximity depends on the type of objects and their representation,
especially in discrete space. In 2D, the simplest scenario corresponds to the pair of points.
As followed from Definition 2, the point does not have any dimensional attributes. Thus,
the proximity defines the distance between the points. In the case of an object being
a line segment, its representation considers the set of points that belong to it. The
proximity in terms of HD (Definition 20) computes the minimum distance from the given
point to one of the points belonging to the line segment [98]. An arbitrary shape in 2D
can be the set of its points from the interior or the contour. Similarly to the line segment,
the proximity is defined using HD.
This chapter introduces the Elliptic Line Voronoi Diagram (ELVD), where the proximity
is defined using CED, and overviews the classical approaches, namely the Point Voronoi
Diagram (PVD) and the Line Voronoi Diagram (LVD). The proposed tessellation method
is then analyzed according to its geometric properties and compared with the above
approaches through the experimental examination.
6.1 Voronoi Diagram (VD)
Before discussing the theory behind the Voronoi Diagram (VD) in 2D, consider the formal
definitions of the notions that are used throughout the related sections.
Definition 44 (Site). Consider the finite set S of N objects (for example, points or line
segments). Any point P ∈ R2 is associated with the closest object from S, such that the
entire space is divided into disjoint regions. The elements in S are called sites.
Definition 45 (Voronoi region). Consider the site set S = {s1, s2, . . . , sN }. A Voronoi
region, VRsi, is the set of points that are closer to the site si than to any other site sj:
VRsi = {P ∈ R2 : dHD(P, si) ≤ dHD(P, sj) | si, sj ∈ S, i ̸= j ∈ [1, . . . , N ]} (6.1)
Definition 46 (Voronoi edge). Consider the finite site set S. The set of points, which
are equally distant from two sites, form the Voronoi edge.
Definition 47 (Voronoi vertex). The Voronoi vertex is an intersection point of at least
three Voronoi edges.
Definition 48 (Voronoi Diagram). The Voronoi Diagram (VD) defined on the finite set
of sites S is a union of corresponding Voronoi edges and vertices:
VDS =
i ̸=j,
si,sj∈S
VRsi ∩ VRsj , (6.2)
where VRsi and VRsj denote the Voronoi regions of the sites si and sj correspondingly.
The VD example is illustrated in Figure 6.1. It contains the set of six sites showed as the
red points. The corresponding Voronoi regions (one of them is shown as a filled rhombus)
are bounded by the Voronoi edges (shown as green line segments). Finally, the Voronoi
vertices are marked as orange squares.
64
6.1. Voronoi Diagram (VD)
Figure 6.1: The VD example
6.1.1 Point Voronoi Diagram (PVD)
Depending on the type of objects in the site set, the variety of VDs is identified. This
thesis focuses on two of them, which are directly related to the proposed methodology:
the Point Voronoi Diagram (PVD) and the Line Voronoi Diagram (LVD).
Definition 49 (Point Voronoi Diagram). Consider a finite site set containing N points.
VD computed from such a set is called Point Voronoi Diagram (PVD). PVD tessellates
the space into N convex Voronoi regions.
Figure 6.2a illustrates the example of PVD. The site set contains six red points, whereas
the Voronoi edges are shown as the green line segments.
Property 27 (Voronoi edges in PVD). Voronoi edges are perpendicular bisectors between
each pair of points in the site set. Voronoi edges can be half-infinite [40].
6.1.2 Line Voronoi Diagram (LVD)
In computational geometry, the majority of geometrical scenarios accept the polygonal
representation of the objects [13]. With this regard, the shape contour is approximated
by the polygon, which, in turn, is the set of line segments.
(a) PVD (b) LVD (c) ELVD
Figure 6.2: Various types of VD
65
6. Elliptic Line Voronoi Diagram (ELVD)
Figure 6.3: The example of LVD containing an area
Definition 50 (Line Voronoi Diagram). Consider a finite site set containing points and
line segments. VD constructed from such a set is called Line Voronoi Diagram (LVD).
LVD tessellates the space into N Voronoi regions.
The example of LVD is provided in Figure 6.2b. The site set contains three non-intersecting
line segments shown in red. The Voronoi edges are the green curves.
Property 28 (LVD Voronoi edge between two line segments sharing an endpoint). In
LVD, a Voronoi edge between two line segments sharing an endpoint contains an area [12].
Property 28 highlights the ambiguity of the representation: an area of points corresponds
to multiple sites (Figure 6.3). One solution is to remove the common endpoint [12].
Property 29 (Number of Voronoi vertices and edges in VD of a closed polygon). VD of
a closed polygon with N edges and M reflex vertices contains exactly N + M − 2 Voronoi
vertices and at most 2(N + M) − 3 Voronoi edges [86].
6.1.3 Elliptic Line Voronoi Diagram (ELVD)
In this thesis, it is proposed to use CED (Section 4.1.2) as a proximity measure. It
enables having an alternative representation of a line segment by the pair of its endpoints.
This implies a space tessellation which in special cases degenerates to PVD or LVD.
Definition 51 (Elliptic Line Voronoi Diagram). Consider a site set having points and
line segments. Each line segment is defined by the pair of its endpoints. The Elliptic
Line Voronoi Diagram (ELVD) tessellates the space into N Voronoi regions using CED.
The example of ELVD is shown in Figure 6.2c. The site set has three non-intersecting
line segments of various lengths. Substituting the Euclidean distance by CED leads to
the change in Definition 45 of the Voronoi region.
Definition 52 (Elliptic Line Voronoi region). Let S = {s1, s2, . . . , sN } be the site set.
Each site is either a point or a line segment. The Elliptic Line Voronoi region, VRE
si
, is
the set of points that are closer to the site si than to any other site sj in terms of CED:
VRE
si
= {P ∈ R2 : dCED(P, si) ≤ dCED(P, sj) | si, sj ∈ S, i ̸= j ∈ [1, . . . , N ]} (6.3)
66
6.1. Voronoi Diagram (VD)
Figure 6.4: The Equal Detour Point (EDP) and the Center of the Incircle (CI)
(a) tangents tA, tB , and tC intersect at CI (b) tangents tK , tL, and tM intersect at CI
Figure 6.5: ELVD of the triangle △ABC and the Center of the Incircle (CI)
Property 30 (ELVD and the Center of the Incircle). In ELVD of the triangle, the six
tangents to the Voronoi edges at the points A, B, C, K, L, and M intersect at exactly
one point in the triangle interior, called Center of the Incircle (CI) (Figure 6.4).
Proof. First, consider the proof for the tangents to Voronoi edges, tA, tB , and tC , taken
at the points A, B, and C. According to the hyperbola property [91], tangent to its
branch at some point P ∈ R2 is an angle bisector between the lines connecting P and its
focal points. In relation to △ABC, consider the hyperbola branch that passes through
the point A and has B and C as the focal points. The tangent tA to this hyperbola
branch at the point A bisects the angle BAC (Figure 6.5a). Similarly, tB and tC bisect
the angles ABC and BCA. For the triangle, the angle bisectors intersect at CI [38]. It
implies that tA, tB, and tC intersect at CI.
67
6. Elliptic Line Voronoi Diagram (ELVD)
Second, follow the proof for the tangents to the Voronoi edges, tK , tL, and tM , taken
at points K, L, and M . Consider the hyperbola with the focal points A and C. One
of its branches passes through B and intersects the triangle edge CA at the point M .
According to Property 3, the tangent tM at M is perpendicular to CA (Figure 6.5b).
Similar reasoning can be applied to the remaining points K and L:
tK⊥AB, tL⊥BC, tM ⊥CA (6.4)
The point M belongs to the Voronoi edge which is defined by the hyperbola branch
passing through B, hence, with regard to (4.11):
d2(A, M) − d2(M, C) = d2(A, B) − d2(B, C) (6.5)
The length of the triangle edge CA can be defined by the sum:
d2(A, M) + d2(M, C) = d2(C, A) (6.6)
From (6.5) and (6.6) it is possible to derive:
d2(A, M) = d2(C, A) − d2(B, C) + d2(A, B)
2 (6.7)
Applying similar reasoning to the point K leads to:
d2(A, K) + d2(K, B) = d2(A, B)
d2(A, K) − d2(K, B) = d2(C, A) − d2(B, C)
(6.8)
=⇒ d2(A, K) = d2(C, A) − d2(B, C) + d2(A, B)
2 (6.9)
As can be observed, d2(A, M) = d2(A, K). Analogically, it is possible to derive the
equalities for the remaining line segments. As a result:
d2(K, B) = d2(B, L), d2(L, C) = d2(C, M) (6.10)
Imagine a circle that touches AK and AM at the points K and M correspondingly
and has a center at O. According to the property of tangents to circle [188], they are
perpendicular to the radius at the point of contact. Hence, tK intersects tM at O, and
d2(O, K)=d2(O, M). Under the same property, OA bisects the angle BAC. For a circle
touching BK and BL with the center at O′: O′B bisects the angle ABC, tK intersects
tL at O′, and d2(O′, K)=d2(O′, L). For a circle touching CL and CM with the center at
O′′: O′′C bisects the angle BCA, tM intersects tL at O′′, and d2(O′′, M)=d2(O′′, L).
Let O and O′ be two distinct points. If d2(O′, K)<d2(O, K), then O′′ is located such
that d2(O′′, L)<d2(O′′, M). If d2(O′, K)>d2(O, K), then d2(O′′, L)>d2(O′′, M). Both
statements contradict the equality of d2(O′′, M) and d2(O′′, L). Thus, points O and O′
coincide. In the same manner, it is possible to show that O′ coincides with O′′. So, all
three tangents, tK , tM , and tL intersect at the same point O ≡ O′ ≡ O′′. Eventually,
this point is also an intersection of the bisectors OA, O′B, and O′′C. The bisectors in a
triangle intersect at CI [38]. It implies that tK , tM , and tL intersect at CI.
68
6.1. Voronoi Diagram (VD)
Langer [59] found the reference to the intersection point of the Voronoi edges in ELVD of
the triangle △ABC: the Equal Detour Point (EDP), or the inner Soddy circle center.
Property 31 (ELVD and the Equal Detour Point). In ELVD of the triangle, the Voronoi
edges passing through its vertices intersect at exactly one point in its interior. In the
literature, this point is referred to as the Equal Detour Point (EDP) [176] (Figure 6.4).
Remark 1. EDP is not on the Euler line but the Soddy line [118].
Remark 2. EDP is always inside the triangle. It stems from the fact that the Voronoi
edges are hyperbola branches, which intersect their transverse axis at the points between
the triangle vertices.
Property 32 (EDP in ELVD of the degenerated triangle). In ELVD of the degenerated
triangle, where two points A and B coincide, EDP is located at the point A (or B).
Proof. The proof considers Property 31 and (4.5). Let A coincide with B, and EDP be
located at P . Then, at the point P , the CED values for AB and AC are identical:
d2(A, P ) + d2(B, P ) − d2(A, B) = d2(C, P ) + d2(A, P ) − d2(A, C) (6.11)
Simplification of (6.11) by removing identical terms and substituting d2(A, C) with
d2(B, C) (because of their equality) leads to:
d2(B, P ) + d2(B, C) = d2(C, P ) (6.12)
(6.12) holds true only when P coincides with A and B.
Definition 53 (Soddy circle). Imagine ELVD of the triangle △ABC. The Voronoi
edges pass through its vertices A, B, and C and intersect the edges AB, BC, and
CA at the points K, L, and M correspondingly. Assume rA = d2(A, M) = d2(A, K),
rB = d2(B, L) = d2(B, K), and rC = d2(C, L) = d2(C, M). Let A, B, and C be the
centers of the circles with the radii rA, rB, and rC : C(A; rA), C(B; rB), and C(C; rC)
correspondingly (Figure 6.6). These circles are tangent to each other [161]. The circle
with the center at EDP that is tangent to C(A; rA), C(B; rB), and C(C; rC) is called the
inner Soddy circle [161].
Property 33 (ELVD distance value at EDP). In ELVD of triangle, the distance value
at EDP, equals the diameter of the inner Soddy circle.
Proof. According to Property 31, the Voronoi edges intersect at the common point. The
distance value at this point is identical in the distance fields generated from the edges
of the triangle, namely AB, BC, and CA. As followed from Definition 53, the inner
Soddy circle is tangent to the circles C(A; rA), C(B; rB), and C(C; rC) (Figure 6.6). The
distance between the centers of tangent circles equals the sum of their radii [38]. Since
69
6. Elliptic Line Voronoi Diagram (ELVD)
Figure 6.6: ELVD of the triangle and the inner Soddy circle
EDP is the center of the inner Soddy circle, it is possible to rewrite (4.5) with regard to
the radii and one of the triangle edges, for instance, CA:
dCED(EDP, CA) = d2(EDP, A) + d2(EDP, C) − d2(C, A) (6.13)
dCED(EDP, CA) = (rA + rS) + (rC + rS) − (rA + rC) = 2rS (6.14)
As can be observed from the above equations, the distance value at the center of the
inner Soddy circle equals its diameter.
6.2 Comparison between PVD, LVD, and ELVD
Several factors affect the space tessellation. On one side, it is the distance metric. On the
other side, it is the type of objects in the site set (for instance, points and line segments),
their mutual arrangement, and the difference in size or shape.
6.2.1 Distance Metric
By definition, PVD and LVD rely on HD, whereas ELVD uses CED. A well-known problem
of VD is to find a trade-off between the tessellation precision and the computational
costs [114,140]. The size of the site set, or the discretization level of input shape, has a
direct influence on the costs and efficiency of approach. Especially, for the GPU-methods.
In contrast, ELVD does not depend on a sampling of line segments that form a polygonal
shape, since it takes only a pair of endpoints.
6.2.2 Types of Objects in the Site Set
Generally speaking, the Voronoi edge in PVD is a bisector, and in LVD – parabolic arcs,
line segments, and rays [116]; in ELVD the Voronoi edge is a multifocal hyperbola branch
70
6.2. Comparison between PVD, LVD, and ELVD
that, in special cases, is a bisector or a hyperbola branch. Here, the Voronoi edges in
classical VD and ELVD are compared for the pairs of objects: line segments and points.
Point and Point
When the site set contains only points, ELVD produces the same results as PVD with
the Euclidean metric (Figure 6.7). The Voronoi edges are the bisectors.
Figure 6.7: Identical PVD (yellow) and ELVD (green) from the site set of points
Point and Line Segment
ELVD separates the point and the line segment with the multifocal hyperbola branch, or
a higher-order curve (Figure 6.8). Depending on the distance between P3 and P1P2 and
the line segment length, the Voronoi edge changes visibly (Figures 6.8a and 6.8b).
(a) d2(P1, P2) ̸= d2(P2, P3) (b) d2(P1, P2) = d2(P2, P3)
Figure 6.8: LVD (yellow) and ELVD (green) from the point and the line segment
71
6. Elliptic Line Voronoi Diagram (ELVD)
(a) d2(P1, P2)<d2(P2, P3) (b) d2(P1, P2)=d2(P2, P3)
Figure 6.9: LVD (yellow) and ELVD (green) of the line segments sharing the endpoint
Line Segments that Share an Endpoint
For the line segments having a different length (Figure 6.9a), ELVD is defined by the
hyperbola branch (shown in green). If the line segments have an equal length (Figure 6.9b),
ELVD contains the bisector passing through the common endpoint P2. Note, in this
scenario, LVD contains an area which is rather a disadvantage for a representation. It
means that the set of points have a non-unique mapping to the sites. In relation to
classification problems, such points are equally likely associated with more than one class.
Line Segments that Intersect Each Other
There are multiple ways to intersect two line segments. If the intersection point splits the
line segments into parts of equal length (Figure 6.10a), LVD and ELVD create an identical
tessellation. Otherwise, ELVD is a multifocal hyperbola that varies depending on the
relative size of the line segments and the intersection point position (Figures 6.10b-6.10f).
In special cases, such a Voronoi edge converges into a closed curve around the shortest
parts. Observe the corresponding Voronoi regions in Figures 6.10b to 6.10d and 6.10f
When the line segments overlap, there are two possible scenarios: (1) partial overlap when
P1P2 and P3P4 have the line segment P3P2 in common (Figure 6.10g), (2) enclosure of one
line segment by another when P3P4 is a part of P1P2 (Figure 6.10h). The disadvantage
of LVD in both cases: it contains the area that creates an ambiguity. In ELVD, in the
case of partial overlap, the Voronoi edge is a multifocal hyperbola branch. When P1P2
encloses P3P4, ELVD has no tessellation of space (Property 22).
Line Segments that do not Intersect
Consider that line segments do not intersect each other (Figure 6.11). The Voronoi edge in
ELVD is the multifocal hyperbola branch that is shifted towards the shorter line segment.
72
6.2. Comparison between PVD, LVD, and ELVD
(a) d2(P1, P2)=d2(P3, P4), cross at the center (b) d2(P1, P2)<d2(P3, P4), cross at the center
(c) d2(P1, P2)=d2(P3, P4), d2(P1, O)<d2(P2, O),
where O is an intersection point
(d) d2(P1, P2)=d2(P3, P4), cross not at a center
(e) d2(P1, P2)<d2(P3, P4), P1 ∈ P3P4 (f) d2(P1, P2) ≪ d2(P3, P4), P1 ∈ P3P4
(g) P3 ∈ P1P2, P2 ∈ P3P4 (h) P3, P4 ∈ P1P2
Figure 6.10: The examples of the Voronoi regions corresponding to LVD (yellow, left)
and ELVD (green, right) generated from the pair of intersecting line segments
The equality of both representations happens when both line segments have the same
length and are mirror-symmetric to each other with regard to some axis (Figures 6.11e
and 6.11f). This axis is the Voronoi edge, which is a perpendicular bisector with regard to
the closest pair of focal points connecting the line segments. For example, in Figure 6.11e
the Voronoi edge is perpendicular to P2P4 and P1P3, and in Figures 6.11f – to P2P3.
73
6. Elliptic Line Voronoi Diagram (ELVD)
(a) (b)
(c) (d)
(e) (f)
Figure 6.11: The examples of the Voronoi regions corresponding to LVD (yellow, left)
and ELVD (green, right) generated from the pair of non-intersecting line segments
6.3 Discussion
So far, the presented tessellation method was empirically compared to VD according to
various types of input data. Such a visual inspection provides an intuitive understanding
of geometrical differences between the approaches. This section uses the proposed
evaluation criteria for the shape representation to assess and compare PVD, LVD, and
ELVD. The results are summarized in Table 6.1.
Scope
From the point of representing space tessellation in 2D, the observed approaches do not
have algorithmic limitations and can be extended to 3D. Particularly, generalization of
PVD to higher dimensions preserves the convexity of the Voronoi regions while losing
the linearity in size [12]. This stays true for ELVD of the point sites.
74
6.3. Discussion
VD ELVD
Scope •any 2D shape expressed by the set of points or line segments
•extension to higher dimensions
•identical representations for point sites
Uniqueness unique for the site set
Voronoi edge might contain area Voronoi edge is always a curve
Invariance invariant to rotation, translation, and scaling
Stability every element affects the
representation
stable in the cases satisfying
Property 22
Accuracy double-precision floating-point 3
√
2
2 pixel_edge_length
Efficiency •Sequential:
O(NlogN) [54, 186] O(N × W × H) [83]
•Parallel:
O(N) [167] O(N) [83]
Abstraction enables hierarchical representation
Table 6.1: Evaluation of the representations VD and ELVD
Uniqueness
ELVD, PVD, and LVD provide a unique partitioning of space that depends on the type
and location of objects in the input site set. It is caused by the Euclidean metric used in
these approaches.
As noted in Sections 6.2.2-Line Segments that Share an Endpoint and Line Segments
that Intersect Each Other, LVD may contain an area of points that are associated with
multiple sites (refer to Figures 6.9 and 6.10). It is a disadvantage for a representation
since creating a non-unique association with the sites. One way to solve the problem is
to add a preprocessing step that resolves the ambiguity. For the line segments sharing an
endpoint it is a common practice to make the line segments disjoint [12]. In the case of
overlapping line segments, the ambiguity can be mitigated by restructuring the common
region. ELVD does not require a preliminary decomposition.
Invariance
Since VD and ELVD use the Euclidean distance as a proximity measure, the resultant
representation is invariant to translation and rotation [127]. Applying the normalization
strategy leads to scale invariance [120].
75
6. Elliptic Line Voronoi Diagram (ELVD)
Stability
This property is interpreted as an ability to preserve space tessellation under changes of
input sites. Especially in the digital domain, it relates to inevitable numerical errors that
lead to a different position of sites, their size, or structure [133]. As noted in [10], VD is
not stable under the continuous motion of sites. Indeed, the small change in the sites
implies the small change in VD [133]. In ELVD, the representation is stable in the cases
fulfilling Property 22. Otherwise, it is sensitive to the each element in the site set.
Accuracy
Computing VD with algorithms using exact arithmetic is a cumbersome and expensive
procedure [187]. Practical implementations rely on fixed-precision arithmetic, like single-
or double-precision floating-point [64,71,72,151]. Strzodka et al. [167] propose a GPU
implementation, where, VD is computed with a single-precision floating point accuracy.
To compute ELVD, it is proposed to apply CEFDT2 algorithms for computing separating
curves: Algorithm 5.2 and method of Langer [83]. In this case, the maximum error equals
3
√
2
2 pixel_edge_length (Section 5.6-Accuracy).
Efficiency
There is a variety of methods creating VD [12]. From the complexity point, PVD requires
O(NlogN) time in the worst case [116], where N denotes the number of point-sites.
So the efficient solutions are assumed to fulfil this condition. The sweepline algorithm,
proposed by Fortune [40,54], takes O(NlogN) time and O(N) space for computing PVD
and LVD. The algorithm is sequential with interdependencies between its parts. It makes
further optimization with parallel computation challenging [122]. Yap [186] proposed a
divide & conquer approach for simple curve segments with O(NlogN) complexity. It is a
powerful algorithmic concept considering parallel VD computation for subsets of sites and
merging the results together. Nevertheless, the implementation is not straightforward:
the improper split into subsets causes difficulties while merging [4]. Another conceptually
valuable method is based on incremental insertion [70, 169]. Here, the sites are added
one by one to sequentially update VD. Although, the average complexity reaches O(N),
in the worst case scenario it equals O(N2).
A parallel computation of VD is proposed by Strzodka et al. [167]. The algorithm,
first, assigns to each pixel the numeric label of the nearest site. Second, it thresholds
the derivative applied to pixel labels to obtain VD. This method is suited for GPU
processing, and has a linear complexity. A comparable approach proposed by Langer [83]
also propagates the site labels. In contrast to [167], it uses the precomputed distance
fields to accelerate processing. In addition, ELVD reduces the computational costs since
there is no need in finding the proximity to all points belonging to the line segment.
76
6.4. Summary
6.4 Summary
This chapter further analyzed the distance field based on confocal ellipses from the VD
perspective. In short, ELVD generalizes VD and degenerates to it in the special scenarios,
like the site set containing only points or equally long line segments sharing an endpoint.
From the geometric structure perspective, PVD and LVD are formed by parabolic arcs
and straight lines. This property enables decomposing higher-order curves into a set of
primitive components which are easy to compute. The Voronoi edge in ELVD could be a
straight line, a hyperbola branch, or a multifocal hyperbola branch (higher-order curve).
A possibility of decomposing such a higher-order curve into primitive components could
be a potential question for future research. It is important to note that LVD of line
segments sharing an endpoint requires a preprocessing step to avoid having an area in
the structure. This is not the case for ELVD. The analysis of the ELVD properties in the
case of a triangle enriches the semantic understanding of the proposed representation.
Generalization of these properties to an arbitrary polygonal shape is yet an open question.
77

CHAPTER 7
Elliptic Line Voronoi Skeleton
This chapter is based on the following publication:
Aysylu Gabdulkhakova, Maximilian Langer, Bernhard W. Langer, Walter G. Kropatsch:
Line Voronoi Diagrams Using Elliptical Distances. In Proceedings of the Joint IAPR
International Workshop on Structural, Syntactic, and Statistical Pattern Recognition,
pages 258–267, 2018 [59]
A skeleton is a compact and effective representation that encodes a shape by the set of its
inner points. The desirable characteristics include invariance to transformations (rotation,
translation, scaling), topology consistency, connectivity, and reconstruction. In addition,
it can provide invariance to bending, elongation, decomposition, widening, and warping.
Thus, the skeleton is used in a variety of application domains, such as image compression
and retrieval, character recognition, path planning, and object recognition [10].
When applied to shape representation, 2D skeleton is primarily associated with a set of 1D
curves and the notion of a medial axis. The existing algorithms for computing a skeleton
can be generally classified into digital and continuous [141]. The continuous methods
approximate the shape boundary by a curve or a polygon, work with the real coordinates
of the points, and rely on analytical computation. A group of methods evolves from
VD [114], which preserves topological as well as geometrical information. The Voronoi
Skeleton (VS) is a VD of the site set forming the shape boundary [114]. VS can be
additionally modified by applying specific pruning techniques [8,14,15,81,90,115,155,173],
which crucial property is in preserving the shape topology.
Alternatively, the skeleton can be obtained by the grassfire transform [25]. Consider a set
of fire fronts that are uniformly propagated from the shape boundary towards the interior.
Then, the skeleton is a set of quenching points where these fire fronts meet. This idea
is reflected in a group of approaches based on the curve propagation principle [28,144].
79
7. Elliptic Line Voronoi Skeleton (ELVS)
The points of the medial axis are located at certain singularities in, for example, flux
field [159], distance field [74,88], or potential field [2].
The digital approaches rest on geometrical and topological rules to extract the skeleton
from a digital grid [141]. One group of methods, called thinning, performs the iterative
erosion of the pixels starting from the shape boundary using the predefined templates
under geometrical and topological constraints [87,109,121,142,190]. Another group of
approaches performs erosion on the distance field [28,69,144]. It has an advantageous
computational efficiency since using DT and not having a need to perform repetitive
image scans. The disadvantage lies in the difficulty of parallelizing such algorithms [140].
An important drawback of the digital and continuous approaches is their noise sensitivity:
small perturbations on the boundary cause spurious branches in the resultant skeleton.
There are many ways to solve this problem, including the boundary smoothing, polygonal
approximation of the shape, a hierarchy of skeletons, weighting of the seed points [15].
The Elliptic Line Voronoi Skeleton (ELVS) is a continuous approach evolved from ELVD.
As opposed to VS, using CED as a metric leads to a non-medial representation of a
shape approximated by the line segments. This chapter aims at exploring the geometrical
properties of ELVS and compares them to the classical VS.
7.1 Voronoi Skeleton (VS)
The shape representation by means of medial loci was proposed by Blum [25]. It defines
the local symmetries of object by the set of points equidistant to the shape boundary.
Definition 54 (Maximal circle). A circle C(O; r) ∈ R2 is maximal if it is not inside any
other circle C(O′; r′)∈ R2.
Definition 55 (Medial axis). The medial axis of a shape in 2D is formed by the centers
of maximal circles that are bitangent to the shape boundary and are entirely in its interior.
The medial axis with the radius function of the maximal circles is called Medial Axis
Transform (MAT) [25]. MAT represents a 2D shape by the union of curves and arcs
and enables reducing its dimensionality to a 1D set of points. MAT preserves symmetry
and local thickness of shape and it is invariant to rotation and translation. The union
of circles, associated with each skeletal point, reconstructs the original shape [141] in
continuous space and covers the shape in digital space [146].
The Voronoi Skeleton (VS) is computed as an intersection of shape and VD. The shape
boundary divides VS into endoskeleton (interior) and exoskeleton (background). The
endoskeleton shows the internal structure, topology, and metrics of the shape, whereas
the exoskeleton – the adjacency relation to the neighboring objects [114]. The discrepancy
between the medial axis and VS depends on the boundary approximation [132] (Figure 7.1).
Schmitt [148] proved that having an infinite number of points on the boundary leads to
convergence in the limit of VS to the medial axis. In this case, consider the boundary is
80
7.2. Elliptic Line Voronoi Skeleton (ELVS)
(a) medial axis (b) 24 points sampled along the boundary
Figure 7.1: The discrepancy between the medial axis and VS extracted from PVD
(a) medial axis equals VS (b) medial axis (c) VS
Figure 7.2: The discrepancy between the medial axis and VS extracted from LVD
approximated by infinitely many points. Then, the Voronoi region of each point-site is the
line that is orthogonal to the tangent to the shape boundary at that point-site [51]. For a
convex polygon, Lee [86] showed that VS is identical to the medial axis (Figure 7.2a). If
the polygon is non-convex, then the medial axis is a subset of VS (Figure 7.2b and 7.2c).
The same holds true for the piecewise-linear/circular shape boundary. When the boundary
is composed of free-form curves, generally, neither is a subset of the other [132].
7.2 Elliptic Line Voronoi Skeleton (ELVS)
Analogically to VS, the Elliptic Line Voronoi Skeleton (ELVS) is a subset of ELVD. As
opposed to VS, the proposed representation is medial only in special cases.
Property 34 (Line segment length impact in ELVS). In ELVS, a site representing a
long line segment pushes the Voronoi edges towards the smaller line segments.
The barycentric coordinates (Definition 6) illustrate this property intuitively. Consider a
triangle △ABC with the side lengths a, b, and c (Figure 7.3). Its half-perimeter equals
s = 1
2(a + b + c), whereas the area is computed by △ = s(s − a)(s − b)(s − c) [38].
According to Dergiades [42], the homogeneous barycentric coordinates of EDP are:
mA = a + △
s−a
mB = b + △
s−b
mC = c + △
s−c
(7.1)
Consider the formula for the tangent of a half of an internal angle in a triangle [165]:
81
7. Elliptic Line Voronoi Skeleton (ELVS)
Figure 7.3: The interpretation of EDP using the barycentric coordinates

tan Â
2 = (s−b)(s−c)
s(s−a)
tan B̂
2 = (s−a)(s−c)
s(s−b)
tan Ĉ
2 = (s−a)(s−b)
s(s−c)
(7.2)
Then, (7.1) can be transformed by substituting the tangent formulas:

mA = a + s tan Â
2
mB = b + s tan B̂
2
mC = c + s tan Ĉ
2
(7.3)
According to the triangle property [124], the shortest side is opposite to the smallest
internal angle. The sum of all the internal angles of the triangle is 180◦ [124], so the
half-angles range between 0◦ and 90◦. The larger the internal angle – the larger the
tangent of the angle. Applying the above statements to (7.3): the acute angle and the
short length of the edge lead to a small value in the barycentric coordinates. Consider
the examples in Figure 7.4. According to Property 2, the areas of the subtriangles are
proportional to the barycentric coordinates of the point. In the case of acute angle at
the vertex B (Figure 7.4a), mB will have the smallest value among mA and mC . As a
result, the subtriangle formed by EDP, A, and C has the smallest area. The opposite
effect is observed when obtuse angle is at the vertex B (Figure 7.4b).
Corollary 1 (Angle priority in ELVS). An acute angle between the connected sites pushes
the Voronoi vertex away from their common point. An obtuse angle – towards their
common point.
7.3 Comparison between VS and ELVS
VS, in its classical sense, is a medial representation whose points are visually in the
middle of the shape. As followed from Property 34 and Corollary 1, ELVS implicitly
82
7.3. Comparison between VS and ELVS
(a) acute (b) obtuse
Figure 7.4: The acute- and obtuse-angled triangles in the barycentric coordinates
(a) square (b) trapezoid
Figure 7.5: The examples of VS (yellow) and ELVS (green) for convex polygons
prioritizes long line segments and acute angles (Figure 7.5b). Consequently, for the
equilateral polygon without self-intersections, ELVS is identical to VS (Figure 7.5a).
From the geometrical point of view, VS is formed by the points having the same distance
to at least two edges of the polygon. So, for the triangle, VS-exoskeleton contains only the
curves that separate the nearest sides. It is not always the case for the ELVS-exoskeleton.
Property 35. In the obtuse-angled triangle the branches of ELVS passing through the
vertices of the longest edge might cross each other twice: in endo- and exoskeleton.
Proof. According to Sections 4.2.1-Bisector and Hyperbola Branch, in ELVS two line
segments with a common endpoint are separated by a bisector or a hyperbola branch. In
Figure 7.6, the hyperbola branch that passes through A separates AB and AC, whereas
the hyperbola branch that passes through C separates AC and BC. The area shows
83
7. Elliptic Line Voronoi Skeleton (ELVS)
the Voronoi region(s) corresponding to AC. With regard to (4.5) and (6.3), the Voronoi
region of AC satisfies:
d2(A,P)+d2(C,P)−d2(A,C)< d2(A,P)+d2(B,P)−d2(A,B)
d2(A,P)+d2(C,P)−d2(A,C)< d2(C,P)+d2(B,P)−d2(C,B)
(7.4)
d2(C,P)−d2(B,P)< d2(A,C)−d2(A,B)
d2(A,P)−d2(B,P)< d2(A,C)−d2(C,B)
(7.5)
It suffices to prove that only for the obtuse-angled triangle (Figure 7.6d), the skeletal
branches might intersect each other twice: in endo- and exoskeleton. To show that,
consider all combinations of the side lengths in △ABC as compared to AC. First, if
△ABC is an equilateral triangle, the respective ELVS contains bisectors that intersect at
CI [5]. Since the bisectors are lines, there is no possibility for them to intersect twice [65].
Second, assume AC is equal to one of the remaining sides, for example, AB. The
skeletal branch passing through A is a bisector. The skeletal branch passing through C
is a hyperbola branch with the foci at A and B. By definition, the hyperbola branch
approaches the asymptotes. To intersect the hyperbola branch, thus, the asymptotes
twice, one condition is to cross the line segment connecting the focal points, AB in this
case, at the point belonging to MB, where M is the middle of AB. This is not possible
since the bisector passes through A. So, there is only one intersection point between a
line containing A and the hyperbola branch that passes through C.
Third, the right sides in system of inequalities (7.5) contain the differences between the
lengths of triangle sides. Here, the upper inequality defines the hyperbola branch passing
through A, whereas the lower – through C. Depending on the sign of the difference,
the resultant hyperbola branch is directed upwards (for plus) or downwards (for minus).
Consider now the remaining configurations of the side lengths by assigning the right sides
in system of inequalities (7.5) to plus or minus.
1. AB and BC are longer than AC (Figure 7.6a), or:
d2(C,P)−d2(B,P)<“—”
d2(A,P)−d2(B,P)<“—”
(7.6)
Both hyperbola branches are directed downwards, leading to a single Voronoi region
related to AC. Consequently, ELVS contains two branches corresponding to AC.
2. AB is shorter and BC is longer than AC (Figure 7.6b), or:
d2(C,P)−d2(B,P)<“+”
d2(A,P)−d2(B,P)<“—”
(7.7)
84
7.3. Comparison between VS and ELVS
(a) d2(A, C)<d2(A, B), d2(A, C)<d2(C, B) (b) d2(A, C)>d2(A, B), d2(A, C)<d2(C, B)
(c) d2(A, C)<d2(A, B), d2(A, C)>d2(C, B) (d) d2(A, C)>d2(A, B), d2(A, C)>d2(C, B)
Figure 7.6: The Voronoi edges in the triangle depending on the side lengths
The hyperbola branch passing through A is directed upwards, and the one passing
through C – downwards. It makes it impossible to have more than one Voronoi
region related to AC.
3. AB is longer and BC is shorter than AC (Figure 7.6c), or:
d2(C,P)−d2(B,P)<“—”
d2(A,P)−d2(B,P)<“+”
(7.8)
This case is symmetric to the previous: there is one Voronoi region related to AC.
4. AB and BC are shorter than AC (Figure 7.6d), or:
d2(C,P)−d2(B,P)<“+”
d2(A,P)−d2(B,P)<“+”
(7.9)
The hyperbola branches passing through A and C are directed upwards. Depending
on the magnitude of the obtuse angle, these branches can intersect twice: in endo-
and exoskeleton.
85
7. Elliptic Line Voronoi Skeleton (ELVS)
VS ELVS
Scope •any 2D shape expressed by the set of points or line segments
•extension to higher dimensions
•identical representations for point sites
medial representation non-medial representation
Uniqueness unique for the site set
Invariance invariant to rotation, translation, and scaling
Stability every element affects the
representation
stable in the cases satisfying
Property 22
can be improved by pruning, smoothing, and weighting [15,115]
Accuracy double-precision floating-point 3
√
2
2 pixel_edge_length
Efficiency •Sequential:
O(NlogN) [75, 86] O(N × W × H) [83]
•Parallel:
O(N) [167] O(N) [83]
Abstraction enables hierarchical representation
Table 7.1: Evaluation of the representations VS and ELVS
7.4 Discussion
Despite a vast amount of literature on this topic, there is no universal definition or
evaluation strategy for skeletons [141]. Thus, similar to the previous sections, VS and
ELVS are compared with respect to the shape representation criteria. The results are
summarized in Table 7.1.
Scope
Similar to VS, ELVS can successfully represent any 2D object. As an example, consider
the skeleton of an elephant shape from the MPEG-7 dataset [160] (Figure 7.7). The
computational efficiency since computing fewer Voronoi regions comes at the price of
skeleton accuracy. Infinitely many point sites along the boundary lead to the medial
axis [148]. The skeletons of the polygons having 50 line segments (Figures 7.7a and 7.7b)
contain less spurious branches than the skeletons generated from the polygons containing
170 line segments (Figures 7.7c and 7.7d). Nevertheless, the skeleton from 50 line segments
reflects fewer details of the shape.
VS is a medial representation: its skeletal points are equally distant from the opposite
borders of the shape. ELVS implicitly prioritizes the long line segments. In Figure 7.7e,
the polygonal approximation contains the line segments of approximately similar length.
86
7.4. Discussion
(a) VS from 50 line segments (b) ELVS from 50 line segments
(c) VS from 170 line segments (d) ELVS from 170 line segments
(e) VS and ELVS for uniform sampling (f) VS and ELVS for non-uniform sampling
Figure 7.7: VS and ELVS of the polygonal approximation of the elephant shape
87
7. Elliptic Line Voronoi Skeleton (ELVS)
The deviation between the trunks in VS and ELVS is comparably small. When the
sampling is not uniform (Figure 7.7f), the shift between VS and ELVS is clearly stronger.
Langer [83] analyzed the effect of varying density in polygons on ELVS: in fact, the
strength of the non-medial shift depends not only on the line segment length but also on
the distance to the opposite line segment.
Similar to VD and ELVD (Section 6.3-Scope), VS and ELVS are transferable to higher
dimensions. For example, the generalization of VS in 3D can be found in [7, 107,156].
Uniqueness
The original shape can be completely and unambiguously reconstructed from Blum’s
representation of the medial axis [25]. This property indicates the presence of one-to-one
mapping between the MAT and the shape. In relation to VS, the MAT procedure can
be repeated when attributing the points of the Voronoi edges with the distance value.
Regarding ELVS of the polygonal shape, the reconstruction process implies collecting
points with the zero distance value in CEFDT2 .
Invariance
When VS and ELVS use the Euclidean distance as a proximity measure, the resultant
representation is invariant to translation, rotation [127], and scaling [16,120].
Stability
VS is highly prone to local perturbations on the boundary. Attali et al. [6] claim that the
small modifications of shape introduce rather local spurious branches and do not highly
influence the entire medial axis. Also, to preserve the topology and subtle details of the
natural shapes, it is needed to have an accurate approximation with a high number of
vertices [148]. In turn, each vertex induces the creation of additional spurious branches
that do not correspond to the essential parts of this shape [115]. To guarantee stability,
VS requires an additional pre/post-processing step for reducing the noise impact and
make the skeleton closer to the medial axis [145]. Various authors introduced the residual
functions for distinguishing curves that correspond to spurious branches from those that
capture the essential parts of the object. Ogniewicz et al. [114,115] propose the attribution
of VS with supplementary information like measures of prominence and stability. Other
pruning measures include, but are not limited to region reconstruction [8,14], residual
branch length [90], bending ratio [155], collapsed boundary length [173], and visual
contribution [15]. The preprocessing steps, such as boundary smoothing [129] or shape
blurring [45], also cause the insensitivity of the representation to redundant artefacts.
Establishing pruning techniques for ELVS is a question for future research. In principle,
the idea of attributing the skeletal points with a measure of significance is applicable
to ELVS. Implicitly, there is already a prioritization of longer line segments and acute
angles (Property 34) implying the noisy parts of the boundary to have shorter branches
in the resultant skeleton.
88
7.5. Summary
Accuracy
The computational precision of VS and ELVS follows the results of VD and ELVD. In
Section 6.3-Accuracy, the methods for VD are computed in a fixed-precision arithmetic [75,
86,167]. The maximum error of the proposed in [83] algorithm is 3
√
2
2 pixel_edge_length.
Efficiency
Since VS and ELVS are derived from VD and ELVD, the worst-case complexity of the
VS algorithms equals O(NlogN) and O(N) for GPU implementation [75, 86,167]. Here,
N denotes the number of sites. Aggarwal et al. [1] presented a linear-time method for
computing VD of a convex polygon.
Due to VD logic, VS contains elementary peripheral branches that do not correspond to
significant parts of the shape [145]. Also, the higher sampling density increases the costs
of pruning the spurious branches. Therefore, the methods from this category consider a
trade-off between the accuracy of the medial axis and the computational costs [140].
Since ELVS is based on ELVD, the respective algorithms can be used to compute a
skeleton. For instance, Langer [83] proposed a linear-time algorithm for ELVS.
Abstraction
The medial axis concisely represents the shape and captures even its subtle details.
Hierarchical approaches enable adapting the representation for the needs of the particular
application by weighting the sites according to their importance [33,44,115].
7.5 Summary
One practical application of ELVD is skeletonization. As follows from the properties,
ELVS implicitly prioritizes the longer edges and acute angles. This fact has an implication
on the structure of the skeleton – in general, it is non-medial and is shifted towards
the smaller edges. Only in special cases, ELVS is identical to VS. Such an implicit
prioritization might cause the intersection of the pair of skeletal branches twice – in exo-
and endoskeleton. This is not the case for VS.
89

CHAPTER 8
Applications
The previous chapters presented the theoretical findings connected to conics and their
generalizations. From the computer vision perspective, there exist problems that are
geometric in nature. Consider the application-driven solutions that would benefit from
the approaches taking their roots from the generalized conics.
8.1 Shape Smoothing
This section is based on the following publication:
Aysylu Gabdulkhakova, Maximilian Langer, Bernhard W. Langer, Walter G. Kropatsch:
Line Voronoi Diagrams Using Elliptical Distances. In Proceedings of the Joint IAPR
International Workshop on Structural, Syntactic, and Statistical Pattern Recognition,
pages 258–267, 2018 [59]
Shape smoothing is an approach to obtain the scale-space representation by preserving
significant details and vanishing the irrelevant ones [73]. In particular, the robustness of
the medial representations such as VS highly depends on the presence of noise along the
boundary [114]. Hence, one purpose of the shape smoothing approaches lies in mitigating
the effect of contour perturbations to improve the reliability of further processing.
8.1.1 State-of-the-Art
A variety of existing techniques relies on region and contour features for smoothing. The
first group of methods performs the shape smoothing by pruning its medial axis [67,115].
The spurious branches do not correspond to the descriptive shape structure. The idea
rests on keeping the skeletal points which measure of prominence is above the threshold.
For the measure of prominence, Ho et al. [67] focused on the distances between the chord
91
8. Applications
(a) angles are comparably similar (b) vertex B has a much smaller angle
(c) vertex B has a much larger angle
Figure 8.1: EDP (square) and mean (diamond) depending on the angles of the triangle
or arc of maximal disk and the corresponding boundary points. Ogniewicz et al. [115]
introduce a set of residual functions assuming the skeletal branches deep in the shape
interior to be less sensitive to the boundary perturbations. By varying the pruning
parameters it is possible to achieve a multiscale representation.
The contour-based methods smooth a particular feature in the local neighborhood of the
points along the boundary. This feature can be, for example, pixel coordinates [104] or
local curvature [73]. Special interest in this category is dedicated to iterative convolution
with the Gaussian kernel. As proposed by Witkin [182], such a process enables vanishing
minor features, namely zero-crossings, while preserving the essential characteristics of
the shape. Changing the variance value creates a multiscale representation of the original
shape [80, 93, 182]. Lindeberg [89] formulated the scale-space theory for the discrete case.
The stability of the existing shape smoothing methods varies over the scale changes [182].
At the coarsest level, the presented techniques do not enable preserving the significant
subtle details of the shape, such as sharp corners. The original global shape parameters,
such as area, are also influenced during the iterative smoothing procedure.
8.1.2 Equal-Detour-Point-based Contour Smoothing
Consider a shape boundary formed by a set of points. Let each triplet (A, B, C) of its
successive points define a triangle △ABC. The straightforward approach is to substitute
iteratively the vertex B by the mean of all three vertices A, B, and C (the similar idea
for 3D can be found in [183]). In Figure 8.1, the mean location for various triangles is
marked with the diamond. As can be seen, the mean is equidistant to all vertices of the
triangle, independent of the angle associated with the vertex B.
92
8.1. Shape Smoothing
Langer [59] proposed the smoothing approach based on an assumption that the boundary
outliers are characterized by an acute angle at the vertex B. As follows from Corollary 1,
the acute angles push Equal Detour Point (EDP) (marked with the square) away from
the corresponding vertex (Figure 8.1a and 8.1b) while keeping it relatively close to the
vertex with the obtuse angle (Figure 8.1c).
Without loss of generality, the properties of EDP provide the following advantages for
shape smoothing. First, in the presence of strong outliers (like in Figure 8.1b), EDP
is much closer to AC than the mean. Thus, it would take fewer iterations to smooth
such a part of the contour. Second, when the angle at the vertex B is obtuse, EDP is
spatially close to the vertex B. Consequently, the magnitude of smoothing decreases
as compared to the mean. Finally, according to Property 32, the proposed approach
provides a possibility of preserving the sharp corners or important details by keeping the
original position of the corresponding points. It can be done by including such points
twice in the contour: the triangle degenerates into a line segment, and EDP coincides
with the duplicated point.
8.1.3 Experimental Results
The criteria for assessing the shape smoothing techniques depend on the features that are
intended to be removed while keeping those that are considered being essential. In this
section, the goal is to assess the stability of preserving the original shape while applying
multiple iterations of smoothing. The shapes are taken from the MPEG-7 dataset [160].
The experimental setup considers two scenarios. First, the proposed method is compared
to the conventional approach, called mean-based smoothing, where the middle point is
iteratively substituted by the mean of the corresponding triplet of consecutive points.
The comparison is performed on the polygonal shape of the flower that has perturbations
along the contour (Figure 8.2). The proposed method affects the high frequencies more
than the low frequencies. With an increase in the smoothing iterations (from 1 to 20)
it preserves the stability stronger than the mean-based smoothing strategy. The visual
inspection of the results shows that the proposed approach has a lower degree of shrinking
and higher preservation of the original shape.
The second scenario is intended to demonstrate the detail preservation of certain parts of
the shape while smoothing the other parts. Consider the shape of the deer (Figure 8.3).
Imagine a necessity of keeping the subtle details of one horn and of the hair on the
neck (highlighted in red in Figure 8.3). In this case, the corresponding points are inserted
again after their first entry. As a result, independent of the number of smoothing
iterations, the area containing the duplicates remains the same. Observe the difference
between the smoothed contours after 100 iterations with detail preservation (Figure 8.3a)
and without (Figure 8.3b). Such functionality cannot be achieved with mean-based
smoothing without changing the algorithm.
93
8. Applications
(a) mean-based
(b) EDP-based
Figure 8.2: The comparison of the smoothing results after 1, 10 and 20 iterations
(a) certain details (red) are preserved (b) complete contour is smoothed
Figure 8.3: The comparison of the smoothing results after 100 iterations
94
8.2. Optimal Path Planning
8.2 Optimal Path Planning
This section is based on the following publication:
Aysylu Gabdulkhakova, Walter G. Kropatsch:
Generalized conics: properties and applications. In Proceedings of the International
Conference on Pattern Recognition, pages 10728–10735, 2020 [57]
The demand for optimal path planning algorithms comes from a wide variety of fields,
such as robotics, computer graphics, geographic information systems, architectural and
VLSI design [22]. The problem is geometric in nature and is concerned with the question
of finding a sequence of moves that bring the object from the source to the destination.
The environment might additionally contain the disjoint obstacles that are supposed to
be avoided. The optimality of the collision-free path is evaluated according to the overall
length and smoothness [22, 61,185].
8.2.1 State-of-the-Art
The optimal path planning is a thoroughly and continuously researched topic with a great
variety of approaches [61, 185]. With the reference to classification in [61], this section is
related to a particular category of the global approaches called the roadmap methods.
The global approaches consider the complete map of environment to be provided a priori.
By definition, a roadmap is a set of curves that express possible collision-free paths
in the given map [84]. The idea is to connect the source and the destination to the
roadmap, in order to find the shortest path between them. A group of approaches uses
VD to compute the roadmap [22, 36, 179]. According to Definition 46, the resultant
curves are equidistant to the obstacles and, thus, are at the maximum possible distance
from them. Consequently, the obtained path is not optimal, despite the computational
efficiency [61]. Therefore, VD-based algorithms are combined with other techniques to
improve optimality in the sense of path length [22,179].
8.2.2 Elliptic-Line-Voronoi-Diagram-based Optimal Path Planning
Elliptic Line Voronoi Diagram (ELVD) is beneficial for optimal path planning applications.
Let the map contain the set of line segments and polygonal objects that represent the
obstacles. Each point in ELVD corresponds to the smallest increment to the length of
at least two line segments from the set of obstacles. As confirmed by Property 34, the
longer line segment pushes the Voronoi edges towards the shorter line segments. The
advantage of such a non-centered representation is lower curvature at sharp corners. In
practice, the vehicles using the ELVD-based trajectory could turn at a higher speed as
compared to VD-based trajectory.
95
8. Applications
(a) VD (b) ELVD (c) VD-based path (d) ELVD-based path
Figure 8.4: The comparison of VD and ELVD of the spiral and the corresponding paths
8.2.3 Experimental Results
First, the evaluation setup compares the path lengths extracted from VD and ELVD.
The long edge prioritization leads to a shift from the medial representation. This effect
is illustrated in Figure 8.4. The map is a union of rectangles with different lengths but
the same width. According to Definition 46, each point in VD is equidistant to at least
two boundaries of the shape (Figure 8.4a). In contrast, in ELVD there is a visible shift
towards the corner that corresponds to the shorter border (Figure 8.4b). To have a
quantitative comparison of the path length, let the green circle be a source and the red
square – a destination (Figures 8.4c and 8.4d). Let the size of the bounding box around
the spiral be 500 by 500 pixels. The VD-based path length equals 1387 pixels, whereas
the ELVD-based path length – 1290 pixels. In this case, ELVD provides a more optimal
path with respect to the length and lower curvature at the sharp corners.
Another example shows the map containing the set of obstacles that need to be avoided.
It has six blue rectangles representing the obstacles and one bounding rectangle limiting
the space (Figure 8.5). The green circle is the source, and the red square is the destination.
The shortest path connecting them is highlighted in red. In Figures 8.5a and 8.5b, the
map is symmetric, the obstacles have an identical width and various lengths. From the
visual observation, the Voronoi edges in ELVD are spatially closer to the obstacles. This
leads to ELVD being more compact. Indeed, for the bounding box size is equal to 400 by
400 pixels, the total number of pixels in ELVD is 3712 (as opposed to 4392 in VD).
Second, the long edge prioritization causes structural differences between VD and ELVD.
The Voronoi edges in VD separate the Voronoi regions of the neighboring objects. Such
neighboring objects have no other object between them. Consider the VD example in
Figure 8.5a. Each pair of the neighboring obstacles has a common Voronoi edge. In
particular, note the Voronoi edge between a pair of yellow rectangles. In ELVD, the
non-neighboring large obstacles can still have a common Voronoi edge. In Figure 8.5b,
such an edge separates a pair of yellow rectangles. So, the Voronoi edge separating a pair
of neighboring obstacles in VD is not present in ELVD. And the other way round. The
Voronoi edge between a pair of non-neighboring obstacles in ELVD is not present in VD.
96
8.3. Optimal Facility Location
(a) VD-based path (b) ELVD-based path
Figure 8.5: The comparison of VD and ELVD of the set of rectangles and their paths (red)
8.3 Optimal Facility Location
This section is based on the following publication:
Aysylu Gabdulkhakova, Walter G. Kropatsch:
Generalized conics: properties and applications. In Proceedings of the International
Conference on Pattern Recognition, pages 10728–10735, 2020 [57]
The problem of finding an optimal facility location is a classical optimization task [21].
It aims at finding a facility location that minimizes the sum of weighted distances to the
given set of N point-locations with the positive weights w1, w2, ..., wN . In principle, the
point-location can be associated with a negative weight. In this case, its distance to the
facility is maximized [111].
8.3.1 State-of-the-Art
In the literature, the optimal facility location problem is known under various names:
minimum distance sum problem [100,150], single facility location problem [105], Fermat-
Weber problem [19, 29]. The original formulation dates back to Fermat and Torricelli
and considers only three points [108,174,175]. The solution for this particular scenario is
referred to as Fermat point of a triangle [163]. Later, from the historical perspective, it
became the first step in location theory and was related to the problem of locating the
facility at a minimum transportation cost [180]. The existing methods include but are
not limited to exact analytical solutions, enumeration of all the possible combinations,
approximate statistical and heuristic methods, and linear programming [19,21,29,100,
139,150,181]. The complexity of the problem increases with the number of points [17],
causing the analytical or iterative solutions to become computationally expensive.
8.3.2 Optimal Facility Location from the Generalized Conics
As can be observed, the formulation of the optimal location problem with positive
weights fits into multifocal ellipse (Definition 15), whereas with the positive and negative
97
8. Applications
weights – into multifocal hyperbola (Definition 16). Thus, the solution is found by
extracting the point from CMEF (or CMHF) with the smallest associated distance
value. The implementation considers, first, computing DT2s for the given set of N point-
locations. Second, taking the pixel-wise sum among all these distance fields. Finally, the
pixel associated with the smallest distance value defines a solution. The computational
complexity equals O(N ×W ×H), where W is the width, and H is the height of the image
containing the area of interest. The parallel algorithm for CMEF enables loading the
precomputed DT2 and transferring the distance values with regard to N point-locations.
The sums can be computed on a pixel-level leading to the total complexity of O(N).
This idea in relation to CEF is explained in [83]. The complexity of finding the minimum
distance value equals O(W × H).
(a) all point-locations have identical weight (b) the point-locations have various weights
(c) the point-locations have positive and negative weights
Figure 8.6: The example of optimal facility location. The green circles correspond to
seven point-locations, and the red square is the facility location. The level sets show the
distance value distribution in CMEF (a)-(b) and CMHF (c)
8.3.3 Experimental Results
The results of the algorithm are illustrated in Figure 8.6. Consider an image showing a
contour of Austria, where the green circles are the cities (point-locations) and the red
square is the desired facility location. In Figures 8.6a and 8.6b, all the weights at the
point-locations are positive, therefore, the red point corresponds to the global minimum
of CMEF. Note, if there is an even number of collinear point-locations, there is more
than one global minimum (Property 9). In Figure 8.6a, the point-locations have identical
weights, as opposed to Figure 8.6b. As a result, the facility location is shifted towards the
98
8.4. Shape Representation
point-locations with the greater weights. Figure 8.6c illustrates the case when the weights
have different signs: positively weighted point-locations attract the global minimum,
whereas the negatively weighted – repulse.
So far the distance between two point-locations is measured with the Euclidean metric.
To have a realistic picture, it is possible to apply the geodesic distance on the binary
image of roads. Instead of a line segment connecting two point-locations, there will be a
shortest path along the roads.
8.4 Shape Representation
This section is based on the following publication:
Aysylu Gabdulkhakova, Walter G. Kropatsch:
Generalized conics with the sharp corners. In Proceedings of the Iberoamerican Congress
on Pattern Recognition, pages 419–429, 2021 [58]
Shape representation is a fundamental part of solving any computer vision problem [39].
The intention is to efficiently preserve the essential object characteristics which depend
on the requirements of a particular application [92]. It can work on a boundary level
or consider the complete set of pixels belonging to the object. For example, Chapter 7
introduced ELVS which enables representing the internal structure of 2D shape using a
set of 1D curves. This section intends to raise interest in the possibility of representing
the shape boundary by using the properties of generalized conics (Chapter 3).
In order to specify a generalized conic, one needs locations of focal points, their associated
weights, and the value of constant weighted sum. Consider the examples in Figure 8.7,
where the locations of three focal points are fixed while changing the value of the constant
weighted sum (Figure 8.7a) or the weights (Figure 8.7b). As can be observed, if the
weights are all positive, then the generated shape is convex, whereas the concavities
are obtained by introducing the negatively weighted focal point(s). Note the variety
of complex shapes generated from the triplet of points. The computation of confocal
generalized conics is performed efficiently by taking the pixel-wise sum of DT2s generated
from the focal points. In contrast, finding an analytical representation of such shapes has
a higher computational complexity: the degree of the corresponding polynomial increases
with every additional focal point [112]. Imagine the representational complexity of other
descriptors, like polygons or splines.
The idea for the future work is to research the possibility of representing a complex shape
by finding an appropriate number of focal points, their locations, weights, and the value
for the sum of weighted distances. What is the minimum number of focal points that
represent or approximate the shape? What is the best possible approximation of the
shape for the given number of focal points? What shapes can be represented with the
generalized conics? As can be observed, all the parameters are numeric. Thus, one way
to answer such questions could be connected to using the advances of machine learning.
99
8. Applications
(a) varying the value of distance sum to the focal points
(b) varying the weights of the focal points
Figure 8.7: The examples of shapes generated from the same triplet of focal points
(a) egg-shape (b) hyperbolic shape
Figure 8.8: The examples of generalized conics with corners
A particular scenario – an egg-shape (Figure 8.8a) or a hyperbolic shape (Figure 8.8b)
with corner. On one side, it is possible to compute the parameters of such shapes given a
boundary. On the other side, as compared to an ellipse, these shapes require only one
additional parameter – the weight of focal point at the corner. Hence, the egg-shape and
the hyperbolic shape enrich the ellipse advantages in the related applications.
100
CHAPTER 9
Conclusion
There is no branch of mathematics, however abstract, which may not some
day be applied to phenomena of the real world.
Nikolai Ivanovich Lobachevsky
Computer vision is a scientific field whose central purpose is to gain semantic information
about the environment from a digital image. It implies a selection of features providing a
meaningful representation of objects. In this regard, mathematics introduces a language
that enables translating a physical entity into a computational model. The richer the
vocabulary – the broader the information spectrum describing the object. This thesis
introduces the new word into the shape representation dictionary – generalized conics.
Conceptually, the generalized conics are the extension of primitives already used in image
processing – a circle and an ellipse. Consequently, the relatively familiar geometric
properties are generalized by accepting infinitely many focal points. It implies an
establishment of a single theoretical framework that qualitatively enhances the explanation
of existing ideas while presenting the advantages of the generic entity.
Apart from the study of geometrical concepts, this thesis exploits the identified properties
of the generalized conics in the image processing domain. The proposed methods, on one
side, generalize the existing shape representations based on the distance fields. On the
other side, they enrich the variety of semantic information connected to the corresponding
representation while improving the computational efficiency. The practical part of the
thesis exemplifies the application scenarios, where the explored properties and methods
are beneficial compared to the state-of-the-art.
The central question underlying this work is connected to the ways of measuring the
distance from a point to an object. A classical approach finds a pair of the closest points.
101
9. Conclusion
In the specific cases, this implies the need for object discretization. This thesis proposes
the alternative solutions based on the properties of the generalized conics:
• Confocal-Ellipse-based Distance (CED) – metric for computing the distance between
the points on confocal ellipses. Since an ellipse can degenerate into a line segment,
CED is interpreted as a distance between a point and a line segment. Here, the
latter is defined by the endpoints, implying the independence of discretization.
• Confocal Elliptic Field (CEF) – distance field that uses CED as a metric. The level
sets in CEF of a line segment are confocal ellipses. The separating curve takes the
form of a bisector, a hyperbola branch, or a multifocal hyperbola branch (higher-
order curve). In order to compute CEF, it suffices to apply simple operations (ad-
dition, subtraction, and minimum) to several Euclidean Distance Fields (DF2).
• Confocal Multifocal Elliptic Field (CMEF) – distance field containing multifocal
ellipses. Each point in this field is associated with the sum of the distances to the
objects in the set. Convexity of the level sets makes this representation useful for
solving optimization problems. Similar to CEF, it can be decomposed into a set of
DF2s and computed by applying addition and multiplication to them.
• Confocal Multifocal Hyperbolic Field (CMHF) – distance field containing multifocal
hyperbolas. Each point in this field is associated with the difference between the
distance values in a pair of CMEFs. Conceptually, the zero level set is a set of
points equidistant to the given pair of CMEFs.
Eventually, the distance fields that inherit the properties from ellipses or multifocal
ellipses demonstrate the proximity of objects with respect to each other. The distance
fields which are based on the properties of hyperbolas or multifocal hyperbolas show the
regions of closest proximity for each object. Interpreting these notions in the digital space
takes an advantage of the Distance Transform (DT). Let N be the number of points, line
segments, or sites, and W × H be the number of pixels in an image.
• Confocal Elliptic Field in terms of DT (CEFDT) – digital interpretation of CEF with
DT. The computational complexity of implementation reaches O(N × W × H) [83].
• Confocal Multifocal Elliptic Field in terms of DT (CMEFDT) – digital interpretation
of CMEF with DT. The computational complexity equals O(N × W × H).
• Confocal Multifocal Hyperbolic Field in terms of DT (CMHFDT) – digital interpre-
tation of CMHF with DT. Its computational complexity is O(W × H).
• Elliptic Line Voronoi Diagram (ELVD) – space tessellation extracted from CEF. It
can be considered a generalization of the Voronoi Diagram (VD) since providing
identical results for the point-sites. Compared to VD, in the case of connected and
overlapping line segments, the Voronoi edges do not contain area. The efficient
implementation of the algorithm [83] achieves O(N × W × H).
102
• Elliptic Line Voronoi Skeleton (ELVS) – shape representation that is extracted from
ELVD, hence, inheriting its properties. ELVS is a non-medial representation, as
opposed to classical VS or medial axis. ELVS has an implicit prioritization of long
line segments and acute angles. Its computational complexity is O(N ×W ×H) [83].
Each of the above algorithms has a potential for parallel computation. It leads to further
improvement of the computational complexity.
Broadly speaking, the generalized conics might become a promising research direction in
computer vision and image processing. This thesis explores the geometrical properties
of curves obtained from simple operations – addition and subtraction – in 2D space.
The existing literature defines also another type of generalization [60], obtained as a
weighted sum of distance products. Analysing such level sets might further enrich
the representational power of the existing methods. From the perspective of shape
representation, a particular emphasis of this work was on the special case – the generalized
conics with sharp corners. Hence, it would be of interest to establish the correspondences
between the weights and the smooth level sets. Another valuable theoretical prospect is
related to ELVD and the exploration of its dual representation.
Understanding the specific aspects of problem together with knowledge of mathematical
framework enables applying the generalized conics in the practical domain. This thesis
outlined a problem variety, such as shape smoothing, optimal path planning, and optimal
facility location. In shape representation, the generalized conics exhibit a representational
power that might be used to connect machine learning and geometrical structure. Another
idea is related to exploration of geometrical properties in N -dimensional space with an
outlook to data mining algorithms. In particular, it implies the thorough analysis of the
global minimum of confocal generalized conics in the presence of outliers, as well as the
evaluation of its stability with the reference to state-of-the-art approaches. In general,
the extension of the work to higher dimensions has a valuable impact on research and a
variety of applications that can benefit from it.
103

Index
barycenter, 8
bisector, 40
Center of the Incircle, 67
conic section, 9
confocal, 14, 34, 38
ellipse, 11
eccentricity, 11
major axis, 11
minor axis, 11
hyperbola, 12
asymptote, 12
branch, 12, 41
center, 12
conjugate axis, 12
eccentricity, 13
transverse axis, 12
vertex, 12
parabola, 9
directrix, 9
focal distance, 9
focus, 9
vertex, 9
convex hull, 21
coordinate system, 8
barycentric, 8, 81
Cartesian, 8
elliptic, 14
corner, 20
digitization, 47
distance
Chessboard, 49, 52, 53
City-Block, 49, 52, 63
Confocal-Ellipse-based, 34, 36
Euclidean, 8, 49, 63
Hausdorff, 34, 36, 64
distance field, 33
concentric circles, 38
confocal ellipses, 38, 50
Confocal Elliptic Field, 38, 39,
51–53, 55
confocal hyperbolas, 38, 50
Confocal Multifocal Elliptic Field,
44, 52, 97
Confocal Multifocal Hyperbolic
Field, 44, 52, 97
Euclidean Distance Field, 38, 97
receptive field, 39, 51
separating curve, 39, 51
Distance Transform, 49
Chessboard Distance Transform, 52,
53, 55
City-Block Distance Transform, 52,
53
Elliptical Distance Transform, 50
Euclidean Distance Transform, 49,
52, 53
Elliptic Line Voronoi Diagram, 63, 66,
95, 96
Elliptic Line Voronoi Skeleton, 79, 81
Equal Detour Point, 69, 81, 92
Euler line, 69
feature element, 48
Fermat point, 97
generalized conic, 15, 97, 99
105
confocal, 19
egglipse, 15
generalized hyperbola, 15
k-ellipse, 15
multifocal curve, 15
multifocal ellipse, 15, 16, 97, 99
egg-shape, 27, 99
sharp corner, 20
multifocal hyperbola, 15, 18, 97, 99
hyperbolic shape, 30, 99
sharp corner, 26
n-ellipse, 15
oval, 15
polyconic, 15
polyellipse, 15
Tschirnhaus´sche Kurve, 15
geometry
analytic, 7
computational, 4
digital, 4, 47
discrete, 4
Euclidean, 7
higher-order curve, 42
image
binary, 48
digital, 48
level set, 9
line segment, 8
maximal circle, 80
medial axis, 79, 80, 91
Medial Axis Transform, 80
metric, 9
optimal facility location, 97
optimal path planning, 95
pixel, 47, 48
pixel connectivity, 48
point, 7
scalar product, 7
shape
categorization, 3
description, 3, 4
descriptor, 3
representation, 1, 3, 4, 63, 79, 99
criteria, 3
site, 63, 64
skeleton, 79
endoskeleton, 80
exoskeleton, 80, 83
skeletonization, 63, 79
smoothing, 91
Equal-Detour-Point-based, 92, 93
mean-based, 93
Soddy circle, 69
Soddy line, 69
space
digital, 47
Euclidean, 7
Voronoi Diagram, 63, 64, 95, 96
Line Voronoi Diagram, 65
Point Voronoi Diagram, 65
Voronoi edge, 64
Voronoi region, 64, 66
Voronoi Skeleton, 79, 80
Voronoi vertex, 64
106
Bibliography
[1] A. Aggarwal, L. J. Guibas, J. Saxe, and P. W. Shor, “A linear-time algorithm for
computing the Voronoi diagram of a convex polygon,” Discrete & Computational
Geometry, vol. 4, no. 6, pp. 591–604, 1989.
[2] N. Ahuja and J.-H. Chuang, “Shape representation using a generalized potential
field model,” IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 19, no. 2, pp. 169–176, 1997.
[3] O. Aichholzer, F. Aurenhammer, D. Chen, D. Lee, and E. Papadopoulou, “Skew
Voronoi Diagrams,” International Journal of Computational Geometry & Applica-
tions, vol. 9, no. 03, pp. 235–247, 1999.
[4] O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, E. Pilgerstorfer,
and M. Rabl, “Divide-and-conquer for Voronoi diagrams revisited,” Computational
geometry, vol. 43, no. 8, pp. 688–699, 2010.
[5] T. M. Apostol and M. A. Mnatsakanian, New horizons in geometry. The Mathe-
matical Association of America, 2017, vol. 47.
[6] D. Attali, J.-D. Boissonnat, and H. Edelsbrunner, “Stability and computation of
medial axes – a state-of-the-art report,” in Mathematical Foundations of Scientific
Visualization, Computer graphics, and Massive Data Exploration. Springer, 2009,
pp. 109–125.
[7] D. Attali and A. Montanvert, “Computing and simplifying 2D and 3D continuous
skeletons,” Computer Vision and Image Understanding, vol. 67, no. 3, pp. 261–273,
1997.
[8] D. Attali, G. Sanniti di Baja, and E. Thiel, “Pruning discrete and semicontinuous
skeletons,” in Proceedings of the International Conference on Image Analysis and
Processing, 1995, pp. 488–493.
[9] F. Aurenhammer, “Power diagrams: properties, algorithms and applications,”
SIAM Journal on Computing, vol. 16, no. 1, pp. 78–96, 1987.
[10] F. Aurenhammer, “Voronoi Diagrams – a survey of a fundamental geometric data
structure,” ACM Computing Surveys, vol. 23, no. 3, pp. 345–405, 1991.
107
[11] F. Aurenhammer, B. Jüttler, and G. Paulini, “Voronoi Diagrams for parallel halflines
and line segments in space,” in Proceedings of the International Symposium on
Algorithms and Computation, 2017, pp. 7:1–7:10.
[12] F. Aurenhammer and R. Klein, “Voronoi Diagrams,” Handbook of computational
geometry, vol. 5, no. 10, pp. 201–290, 2000.
[13] F. Aurenhammer, R. Klein, and D.-T. Lee, Voronoi Diagrams and Delaunay
triangulations. World Scientific, 2013.
[14] X. Bai and L. J. Latecki, “Discrete skeleton evolution,” in Proceedings of the
International Workshop on Energy Minimization Methods in Computer Vision and
Pattern Recognition, 2007, pp. 362–374.
[15] X. Bai, L. J. Latecki, and W.-Y. Liu, “Skeleton pruning by contour partitioning with
discrete curve evolution,” IEEE Transactions on Pattern Analysis and Machine
Intelligence, vol. 29, no. 3, pp. 449–462, 2007.
[16] X. Bai, X. Yang, D. Yu, and L. J. Latecki, “Skeleton-based shape classification
using path similarity,” International Journal of Pattern Recognition and Artificial
Intelligence, vol. 22, no. 04, pp. 733–746, 2008.
[17] C. L. Bajaj, “The algebraic degree of geometric optimization problems,” Discrete
& Computational Geometry, vol. 3, pp. 177–191, 1988.
[18] G. Barequet, M. T. Dickerson, and M. T. Goodrich, “Voronoi Diagrams for convex
polygon-offset distance functions,” Discrete & Computational Geometry, vol. 25,
no. 2, pp. 271–291, 2001.
[19] A. Baskar, “Analysing a few trigonometric solutions for the Fermat-Weber facility
location triangle problem with and without repulsion and generalising the solutions,”
International Journal of Mathematics in Operational Research, vol. 10, no. 2, pp.
150–166, 2017.
[20] S. Berretti, A. Del Bimbo, and P. Pala, “Retrieval by shape similarity with per-
ceptual distance and effective indexing,” IEEE Transactions on Multimedia, vol. 2,
no. 4, pp. 225–239, 2000.
[21] S. Bespamyatnikh, K. Kedem, and M. Segal, “Optimal facility location under
various distance functions,” in Proceedings of the Workshop on Algorithms and
Data Structures. Springer, 1999, pp. 318–329.
[22] P. Bhattacharya and M. L. Gavrilova, “Voronoi diagram in optimal path planning,”
in Proceedings of the International Symposium on Voronoi Diagrams in Science
and Engineering, 2007, pp. 38–47.
108
[23] P. Bhattacharya and M. L. Gavrilova, “Roadmap-based path planning – using the
Voronoi Diagram for a clearance-based shortest path,” IEEE Robotics & Automation
Magazine, vol. 15, no. 2, pp. 58–66, 2008.
[24] J. Bloomenthal, C. Bajaj, J. Blinn, B. Wyvill, M.-P. Cani, A. Rockwood, and
G. Wyvill, Introduction to implicit surfaces. Morgan Kaufmann Publishers, 1997.
[25] H. Blum, “A transformation for extracting new descriptors of shape,” in Models
for the Perception of Speech and Visual Form. MIT press, 1967, pp. 362–380.
[26] G. Borgefors, “Distance transformations in digital images,” Computer Vision,
Graphics, and Image Processing, vol. 34, no. 3, pp. 344–371, 1986.
[27] G. Borgefors, “On digital distance transforms in three dimensions,” Computer
Vision and Image Understanding, vol. 64, no. 3, pp. 368–376, 1996.
[28] G. Borgefors, I. Nyström, and G. Sanniti di Baja, “Computing skeletons in three
dimensions,” Pattern Recognition, vol. 32, no. 7, pp. 1225–1236, 1999.
[29] P. Bose, A. Maheshwari, and P. Morin, “Fast approximations for sums of distances,
clustering and the Fermat–Weber problem,” Computational Geometry, vol. 24,
no. 3, pp. 135–146, 2003.
[30] M. Brady, “Criteria for representations of shape,” in Human and machine vision.
Elsevier, 1983, pp. 39–84.
[31] J. E. Bresenham, “Algorithm for computer control of a digital plotter,” IBM
Systems Journal, vol. 4, no. 1, pp. 25–30, 1965.
[32] R. A. Brualdi, Introductory combinatorics. Pearson, 2009.
[33] A. Bucksch and R. Lindenbergh, “CAMPINO – a skeletonization method for point
cloud processing,” International Society for Photogrammetry and Remote Sensing
Journal of Photogrammetry and Remote Sensing, vol. 63, no. 1, pp. 115–127, 2008.
[34] L. M. Chen, Digital and discrete geometry: theory and algorithms. Springer, 2014.
[35] L. P. Chew and R. L. (Scot) Drysdale, III, “Voronoi Diagrams based on convex
distance functions,” in Proceedings of the Annual Symposium on Computational
Geometry, 1985, pp. 235–244.
[36] H. Choset and J. W. Burdick, “Sensor-based exploration: the hierarchical Gener-
alized Voronoi Graph,” The International Journal of Robotics Research, vol. 19,
no. 2, pp. 96–125, 2000.
[37] K. C. Ciesielski, X. Chen, J. K. Udupa, and G. J. Grevera, “Linear time algorithms
for exact distance transform,” Journal of Mathematical Imaging and Vision, vol. 39,
no. 3, pp. 193–209, 2011.
109
[38] H. S. M. Coxeter and S. L. Greitzer, Geometry revisited. Mathematical Association
of America, 1967.
[39] L. da Fontoura Costa and R. M. Cesar, Jr., Shape analysis and classification: theory
and practice. CRC Press, 2000.
[40] M. de Berg, O. Cheong, M. van Kreveld, and M. H. Overmars, Computational
geometry: algorithms and applications, 3rd Edition. Springer, 2008.
[41] T. de Zeeuw, “Elliptical galaxies with separable potentials,” Monthly Notices of
the Royal Astronomical Society, vol. 216, no. 2, pp. 273–334, 1985.
[42] N. Dergiades, “The Soddy circles,” Forum Geometricorum, vol. 7, pp. 191–197,
2007.
[43] S. L. Devadoss and J. O′Rourke, Discrete and computational geometry. Princeton
University Press, 2011.
[44] T. K. Dey and W. Zhao, “Approximating the medial axis from the Voronoi Diagram
with a convergence guarantee,” Algorithmica, vol. 38, no. 1, pp. 179–200, 2004.
[45] A. R. Dill, M. D. Levine, and P. B. Noble, “Multiple resolution skeletons,” IEEE
Transactions on Pattern Analysis and Machine Intelligence, vol. 9, no. 4, pp.
495–504, 1987.
[46] G. L. Dirichlet, “Über die Reduction der positiven quadratischen Formen mit drei
unbestimmten ganzen Zahlen,” Journal für die reine und angewandte Mathematik
(Crelles Journal), vol. 40, pp. 209–227, 1850.
[47] H. Edelsbrunner, Algorithms in combinatorial geometry, ser. Monographs in Theo-
retical Computer Science. An EATCS Series. Springer, 1987, vol. 10.
[48] H. Edelsbrunner, “Computational geometry,” in Current Trends in Theoretical Com-
puter Science - Essays and Tutorials (World Scientific Series Computer Science).
World Scientific Publishing, 1993, vol. 40, pp. 3–48.
[49] H. Edelsbrunner, L. J. Guibas, and J. Stolfi, “Optimal point location in a monotone
subdivision,” SIAM Journal on Computing, vol. 15, no. 2, pp. 317–340, 1986.
[50] P. Erdös and I. Vincze, “On the approximation of convex, closed plane curves by
multifocal ellipses,” Journal of Applied Probability, pp. 89–96, 1982.
[51] R. Fabbri, L. F. Estrozi, and L. Da F. Costa, “On Voronoi diagrams and medial
axes,” Journal of Mathematical Imaging and Vision, vol. 17, pp. 27–40, 2002.
[52] I. D. Faux and M. J. Pratt, Computational geometry for design and manufacture.
Horwood, 1979.
110
[53] A. R. Forrest, “II. Current developments in the design and production of three-
dimensional curved objects - Computational geometry,” Proceedings of the Royal
Society A: Mathematical, Physical and Engineering Sciences, vol. 321, no. 1545, pp.
187–195, 1971.
[54] S. Fortune, “A sweepline algorithm for Voronoi diagrams,” Algorithmica, vol. 2, no.
1-4, p. 153, 1987.
[55] M. Foskey, M. Garber, M. C. Lin, and D. Manocha, “A Voronoi-based hybrid
motion planner,” in Proceedings of the IEEE/RSJ International Conference on
Intelligent Robots and Systems, vol. 1, 2001, pp. 55–60.
[56] A. Gabdulkhakova and W. G. Kropatsch, “Confocal ellipse-based distance and
confocal elliptical field for polygonal shapes,” in Proceedings of the International
Conference on Pattern Recognition, 2018, pp. 3025–3030.
[57] A. Gabdulkhakova and W. G. Kropatsch, “Generalized conics: properties and
applications,” in Proceedings of the International Conference on Pattern Recognition,
2020, pp. 10 728–10 735.
[58] A. Gabdulkhakova and W. G. Kropatsch, “Generalized conics with the sharp
corners,” in Proceedings of the Iberoamerican Congress on Pattern Recognition.
Springer, 2021, pp. 419–429.
[59] A. Gabdulkhakova, M. Langer, B. W. Langer, and W. G. Kropatsch, “Line Voronoi
Diagrams using elliptical distances,” in Proceedings of the Joint IAPR International
Workshop on Statistical Techniques in Pattern Recognition and Structural and
Syntactic Pattern Recognition, 2018, pp. 258–267.
[60] G. Glaeser, H. Stachel, and B. Odehnal, The Universe of Conics: From the ancient
Greeks to 21st century developments. Springer, 2016.
[61] C. Goerzen, Z. Kong, and B. Mettler, “A survey of motion planning algorithms
from the perspective of autonomous UAV guidance,” Journal of Intelligent and
Robotic Systems, vol. 57, no. 1, pp. 65–100, 2010.
[62] R. Goldman, “Curvature formulas for implicit curves and surfaces,” Computer
Aided Geometric Design, vol. 22, no. 7, pp. 632–658, 2005.
[63] C. Groß and T.-K. Strempel, “On generalizations of conics and on a generalization
of the Fermat-Torricelli problem,” The American Mathematical Monthly, vol. 105,
no. 8, pp. 732–743, 1998.
[64] M. Held, “VRONI: An engineering approach to the reliable and efficient computation
of Voronoi diagrams of points and line segments,” Computational Geometry, vol. 18,
no. 2, pp. 95–123, 2001.
[65] D. Hilbert, The foundations of geometry. Open Court Publishing Company, 1902.
111
[66] D. Hilbert and S. Cohn-Vossen, “The cylinder, the cone, the conic sections, and
their surfaces of revolution,” in Geometry and the imagination, ser. AMS Chelsea
Publishing. American Mathematical Society, 1999.
[67] S.-B. Ho and C. R. Dyer, “Shape smoothing using medial axis properties,” IEEE
Transactions on Pattern Analysis and Machine Intelligence, vol. 8, no. 4, pp.
512–520, 1986.
[68] F. K. Hwang, “An O(N logN) algorithm for rectilinear minimal spanning trees,”
Journal of the ACM, vol. 26, no. 2, pp. 177–182, 1979.
[69] S. Iglesias-Cofán and A. Formella, “Guided thinning,” Pattern Recognition Letters,
vol. 128, pp. 176–182, 2019.
[70] T. Imai, “A Topology oriented algorithm for the Voronoi diagram of polygons,” in
Proceedings of the Canadian Conference on Computational Geometry, 1996, pp.
107–112.
[71] M. I. Karavelas, “A robust and efficient implementation for the segment Voronoi
diagram,” in Proceedings of the International symposium on Voronoi diagrams in
science and engineering, 2004, pp. 51–62.
[72] M. I. Karavelas and M. Yvinec, “Dynamic additively weighted Voronoi diagrams in
2D,” in Proceedings of the European Symposium on Algorithms, 2002, pp. 586–598.
[73] B. B. Kimia and K. Siddiqi, “Geometric heat equation and nonlinear diffusion of
shapes and images,” Computer Vision and Image Understanding, vol. 64, no. 3, pp.
305–322, 1996.
[74] R. Kimmel, D. Shaked, N. Kiryati, and A. M. Bruckstein, “Skeletonization via
distance maps and level sets,” Computer Vision and Image Understanding, vol. 62,
no. 3, pp. 382–391, 1995.
[75] D. G. Kirkpatrick, “Efficient computation of continuous skeletons,” in Proceedings
of the Annual Symposium on Foundations of Computer Science, 1979, pp. 18–27.
[76] K. Kise, A. Sato, and M. Iwata, “Segmentation of page images using the area
Voronoi Diagram,” Computer Vision and Image Understanding, vol. 70, no. 3, pp.
370–382, 1998.
[77] C. O. Kiselman, Elements Of Digital Geometry, Mathematical Morphology, And
Discrete Optimization. World Scientific, 2022.
[78] R. Klein and D. Wood, “Voronoi Diagrams based on general metrics in the plane,” in
Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science,
1988, pp. 281–291.
112
[79] R. Klette and A. Rosenfeld, Digital geometry: geometric methods for digital picture
analysis. Morgan Kaufmann, 2004.
[80] J. J. Koenderink, “The structure of images,” Biological cybernetics, vol. 50, no. 5,
pp. 363–370, 1984.
[81] D. Kotsur and V. Tereshchenko, “Optimization heuristics for computing the Voronoi
skeleton,” in Proceedings of the International Conference on Computational Science,
2019, pp. 96–111.
[82] V. Kumar, J. K. Chhabra, and D. Kumar, “Performance evaluation of distance
metrics in the clustering algorithms,” INFOCOMP Journal of Computer Science,
vol. 13, no. 1, pp. 38–52, 2014.
[83] M. Langer, A. Gabdulkhakova, and W. G. Kropatsch, “Non-centered Voronoi
Skeletons,” in Proceedings of the International Conference on Discrete Geometry
for Computer Imagery, 2019, pp. 355–366.
[84] J.-C. Latombe, Robot motion planning, ser. The Kluwer International Series in
Engineering and Computer Science. Kluwer Academic Publishers, 1991, vol. 124.
[85] D.-T. Lee, “Two-dimensional Voronoi Diagrams in the Lp-metric,” Journal of the
ACM, vol. 27, no. 4, pp. 604–618, 1980.
[86] D.-T. Lee, “Medial axis transformation of a planar shape,” IEEE Transactions on
Pattern Analysis & Machine Intelligence, vol. 4, no. 4, pp. 363–369, 1982.
[87] T.-C. Lee, R. L. Kashyap, and C.-N. Chu, “Building skeleton models via 3-D medial
surface axis thinning algorithms,” CVGIP: Graphical Models and Image Processing,
vol. 56, no. 6, pp. 462–478, 1994.
[88] F. F. Leymarie and M. D. Levine, “Simulating the grassfire transform using an active
contour model,” IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 14, no. 1, pp. 56–75, 1992.
[89] T. Lindeberg, “Scale-space theory: a basic tool for analyzing structures at different
scales,” Journal of applied statistics, vol. 21, no. 1-2, pp. 225–270, 1994.
[90] H. Liu, Z. Wu, D. F. Hsu, B. S. Peterson, and D. Xu, “On the generation and
pruning of skeletons using generalized Voronoi Diagrams,” Pattern Recognition
Letters, vol. 33, no. 16, pp. 2113–2119, 2012.
[91] E. H. Lockwood, A book of curves. Cambridge University Press, 1961.
[92] S. Loncaric, “A survey of shape analysis techniques,” Pattern Recognition, vol. 31,
no. 8, pp. 983–1001, 1998.
113
[93] C. Lopez-Molina, B. De Baets, H. Bustince, J. Sanz, and E. Barrenechea, “Multiscale
edge detection based on Gaussian smoothing and edge tracking,” Knowledge-Based
Systems, vol. 44, pp. 101–111, 2013.
[94] F. Malmberg, R. Strand, J. Zhang, and S. Sclaroff, “The Boolean Map Distance:
theory and efficient computation,” in Proceedings of the International Conference
on Discrete Geometry for Computer Imagery, 2017, pp. 335–346.
[95] D. Marr and H. K. Nishihara, “Representation and recognition of the spatial
organization of three-dimensional shapes,” Proceedings of the Royal Society B:
Biological Sciences, vol. 200, no. 1140, pp. 269–294, 1978.
[96] C. R. Maurer Jr., R. Qi, and V. Raghavan, “A linear time algorithm for computing
exact Euclidean distance transforms of binary images in arbitrary dimensions,”
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 2,
pp. 265–270, 2003.
[97] J. C. Maxwell, The Scientific Letters and Papers of James Clerk Maxwell: Volume
1, 1846-1862. Cambridge University Press, 1990.
[98] N. Mayya and V. T. Rajan, “Voronoi Diagrams of polygons: a framework for shape
representation,” Journal of Mathematical Imaging and Vision, vol. 6, no. 4, pp.
355–378, 1996.
[99] K. Mehlhorn, Data Structures and Algorithms 3: Multi-dimensional searching and
computational geometry, ser. Monographs in Theoretical Computer Science. An
EATCS Series. Springer, 1984.
[100] L. F. Mello and L. R. dos Santos, “On the location of the minimum point in the
Euclidean distance sum problem,” São Paulo Journal of Mathematical Sciences,
vol. 12, no. 1, pp. 108–120, 2018.
[101] Z. A. Melzak and J. S. Forsyth, “Polyconics. I. Polyellipses and optimization,”
Quarterly of Applied Mathematics, vol. 35, no. 2, pp. 239–255, 1977.
[102] F. Meyer, “Cytologie quantitative et morphologie mathématiques,” Ph.D. disserta-
tion, École nationale supérieure des mines de Paris, 1979.
[103] M. Minsky and S. A. Papert, Perceptrons: an introduction to computational
geometry. MIT Press, 1987.
[104] F. Mokhtarian and A. K. Mackworth, “Scale-based description and recognition of
planar curves and two-dimensional shapes,” IEEE Transactions on Pattern Analysis
and Machine intelligence, vol. 8, no. 1, pp. 34–43, 1986.
[105] E. Moradi and M. Bidkhori, “Single facility location problem,” in Facility Location,
ser. Contributions to Management Science. Physica, 2009, pp. 37–68.
114
[106] J. C. Morrison, “Distance from a point to a line,” in Graphics Gems II. Academic
Press, 1991, pp. 10–13.
[107] M. Näf, G. Székely, R. Kikinis, M. E. Shenton, and O. Kübler, “3D Voronoi
skeletons and their usage for the characterization and recognition of 3D organ
shape,” Computer Vision and Image Understanding, vol. 66, no. 2, pp. 147–161,
1997.
[108] Á. Nagy, “A short review on the theory of generalized conics,” Acta Mathematica
Academiae Paedagogicae Nyíregyháziensis, vol. 31, no. 1, pp. 81–96, 2015.
[109] G. Németh, P. Kardos, and K. Palágyi, “Thinning combined with iteration-by-
iteration smoothing for 3D binary images,” Graphical Models, vol. 73, no. 6, pp.
335–345, 2011.
[110] W. K. Nicholson, Linear algebra with applications. Lyryx Learning Inc., 2020.
[111] S. Nickel and E.-M. Dudenhöffer, “Weber’s Problem with Attraction and Repulsion
under Polyhedral Gauges,” Journal of Global Optimization, vol. 11, no. 4, pp.
409–432, 1997.
[112] J. Nie, P. A. Parrilo, and B. Sturmfels, “Semidefinite representation of the k-ellipse,”
in Algorithms in Algebraic Geometry, ser. The IMA Volumes in Mathematics and
its Applications. Springer, 2008, vol. 146, pp. 117–132.
[113] J. Öfverstedt, J. Lindblad, and N. Sladoje, “Stochastic Distance Transform,” in
Proceedings of the International Conference on Discrete Geometry for Computer
Imagery, 2019, pp. 75–86.
[114] R. Ogniewicz and M. Ilg, “Voronoi skeletons: theory and applications,” in Pro-
ceedings of the Conference on Computer Vision and Pattern Recognition, 1992, pp.
63–69.
[115] R. L. Ogniewicz and O. Kübler, “Hierarchic Voronoi Skeletons,” Pattern Recognition,
vol. 28, no. 3, pp. 343–359, 1995.
[116] A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu, Spatial tessellations: concepts
and applications of Voronoi diagrams. John Wiley & Sons, 2000.
[117] N. Okabe, J.-I. Toriwaki, and T. Fukumura, “Paths and distance functions on
three-dimensional digitized pictures,” Pattern Recognition Letters, vol. 1, no. 4, pp.
205–212, 1983.
[118] A. Oldknow, “The Euler-Gergonne-Soddy triangle of a triangle,” The American
Mathematical Monthly, vol. 103, no. 4, pp. 319–329, 1996.
[119] L. M. Ostresh Jr., “On the convergence of a class of iterative methods for solving
the Weber location problem,” Operations Research, vol. 26, no. 4, pp. 597–609,
1978.
115
[120] D. W. Paglieroni, “Distance transforms: properties and machine vision applications,”
CVGIP: Graphical models and image processing, vol. 54, no. 1, pp. 56–74, 1992.
[121] K. Palágyi and G. Németh, “1-attempt parallel thinning,” Journal of Combinatorial
Optimization, 2021.
[122] A. Paudel, J. Yang, and S. Puri, “Parallelization of Plane Sweep based Voronoi Con-
struction with Compiler Directives,” in Proceedings of the IEEE Annual Computer
Software and Applications Conference, vol. 1, 2019, pp. 908–911.
[123] T. Pavlidis, “A review of algorithms for shape analysis,” Computer Graphics and
Image Processing, vol. 7, no. 2, pp. 243–258, 1978.
[124] O. Perry and J. Perry, Mathematics I. Palgrave Macmillan London, 1981.
[125] J. C. Peterson and R. D. Smith, Mathematics for Machine Technology. Cengage
Learning, 2018.
[126] M. Petrović, B. D. Banjac, B. Malešević, and R. Mijailović, “Curve fitting by
multifocal ellipses in architectural structures geometry,” in Proceedings of the
International Scientific Conference on Geometry and Graphics–moNGeometrija,
2016, pp. 160–164.
[127] M.-T. Pham, O. J. Woodford, F. Perbet, A. Maki, B. Stenger, and R. Cipolla,
“A new distance for scale-invariant 3D shape recognition and registration,” in
Proceedings of the International Conference on Computer Vision, 2011, pp. 145–
152.
[128] C. A. Pickover, The math book: from Pythagoras to the 57th dimension, 250
milestones in the history of mathematics. Sterling Publishing Company, 2009.
[129] S. M. Pizer, W. R. Oliver, and S. H. Bloomberg, “Hierarchical shape description
via the multiresolution symmetric axis transform,” IEEE Transactions on Pattern
Analysis and Machine Intelligence, vol. 9, no. 4, pp. 505–511, 1987.
[130] M. Ponce and P. Santibánez, “On equidistant sets and generalized conics: the old
and the new,” The American Mathematical Monthly, vol. 121, no. 1, pp. 18–32,
2014.
[131] F. P. Preparata and M. I. Shamos, Computational geometry: an introduction, ser.
Monographs in Computer Science. Springer, 1985.
[132] R. Ramamurthy and R. T. Farouki, “Voronoi diagram and medial axis algorithm
for planar domains with curved boundaries I. Theoretical foundations,” Journal of
Computational and Applied Mathematics, vol. 102, no. 1, pp. 119–141, 1999.
[133] D. Reem, “The geometric stability of Voronoi Diagrams with respect to small
changes of the sites,” in Proceedings of the Annual Symposium on Computational
Geometry, 2011, pp. 254–263.
116
[134] W. Richards and D. D. Hoffman, “Codon constraints on closed 2D shapes,” Com-
puter Vision, Graphics, and Image Processing, vol. 31, no. 3, pp. 265–281, 1985.
[135] É. O. Rodrigues, “Combining Minkowski and Chebyshev: new distance proposal
and survey of distance metrics using k-nearest neighbours classifier,” Pattern
Recognition Letters, vol. 110, pp. 66–71, 2018.
[136] A. Rosenfeld and J. L. Pfaltz, “Sequential operations in digital picture processing,”
Journal of the ACM, vol. 13, no. 4, pp. 471–494, 1966.
[137] A. Rosenfeld and J. L. Pfaltz, “Distance functions on digital pictures,” Pattern
Recognition, vol. 1, no. 1, pp. 33–61, 1968.
[138] P. L. Rosin and G. A. W. West, “Multi-scale salience distance transforms,” in
Proceedings of the British Machine Vision Conference, 1993, pp. 579–588.
[139] G. Rushton, Optimal location of facilities. COMPress, 1979.
[140] P. K. Saha, G. Borgefors, and G. Sanniti di Baja, “A survey on skeletonization
algorithms and their applications,” Pattern Recognition Letters, vol. 76, pp. 3–12,
2016.
[141] P. K. Saha, G. Borgefors, and G. Sanniti di Baja, Skeletonization: theory, methods
and applications. Academic Press, 2017.
[142] P. K. Saha, B. B. Chaudhuri, and D. D. Majumder, “A new shape preserving
parallel thinning algorithm for 3D digital images,” Pattern Recognition, vol. 30,
no. 12, pp. 1939–1955, 1997.
[143] P. V. Sahadevan, “The theory of the egglipse - a new curve with three focal points,”
International Journal of Mathematical Education in Science and Technology, vol. 18,
no. 1, pp. 29–39, 1987.
[144] G. Sanniti di Baja, “Well-shaped, stable, and reversible skeletons from the (3, 4)-
distance transform,” Journal of Visual Communication and Image Representation,
vol. 5, no. 1, pp. 107–115, 1994.
[145] G. Sanniti di Baja, “On medial representations,” in Proceedings of the Iberoamerican
Congress on Pattern Recognition, 2008, pp. 1–13.
[146] C. Sansone, D. Pucher, N. M. Artner, W. G. Kropatsch, A. Saggese, and M. Vento,
“Shape normalizing and tracking dancing worms,” in Proceedings of the Joint
IAPR International Workshop on Statistical Techniques in Pattern Recognition and
Structural and Syntactic Pattern Recognition, 2016, pp. 390–400.
[147] B. F. Schaudt and R. L. (Scot) Drysdale, III, “Multiplicatively weighted crystal
growth Voronoi Diagrams,” in Proceedings of the Annual Symposium on Computa-
tional Geometry, 1991, pp. 214–223.
117
[148] M. Schmitt, “Some examples of algorithms analysis in computational geometry by
means of mathematical morphological techniques,” in Proceedings of the French
Workshop on Geometry and Robotics, 1988, pp. 225–246.
[149] T. Schreiber, “A Voronoi Diagram based adaptive k-means-type clustering algo-
rithm for multidimensional weighted data,” in Proceedings of the Workshop on
Computational Geometry, 1991, pp. 265–275.
[150] J. Sekino, “n-ellipses and the minimum distance sum problem,” The American
Mathematical Monthly, vol. 106, no. 3, pp. 193–202, 1999.
[151] S. Sethia, M. Held, and J. S. B. Mitchell, “PVD: A stable implementation for
computing Voronoi diagrams of polygonal pockets,” in Workshop on Algorithm
Engineering and Experimentation. Springer, 2001, pp. 105–116.
[152] M. I. Shamos, “Problems in computational geometry,” Ph.D. dissertation, Yale
University, 1978.
[153] M. I. Shamos and D. Hoey, “Closest-point problems,” in Proceedings of the Annual
Symposium on Foundations of Computer Science, 1975, pp. 151–162.
[154] A. Sheffer, M. Etzion, A. Rappoport, and M. Bercovier, “Hexahedral mesh gener-
ation using the embedded Voronoi graph,” Engineering with Computers, vol. 15,
no. 3, pp. 248–262, 1999.
[155] W. Shen, X. Bai, R. Hu, H. Wang, and L. J. Latecki, “Skeleton growing and pruning
with bending potential ratio,” Pattern Recognition, vol. 44, no. 2, pp. 196–209,
2011.
[156] E. C. Sherbrooke, N. M. Patrikalakis, and E. Brisson, “An algorithm for the medial
axis transform of 3D polyhedral solids,” IEEE Transactions on Visualization and
Computer Graphics, vol. 2, no. 1, pp. 44–61, 1996.
[157] F. Y. Shih, Image processing and mathematical morphology: fundamentals and
applications. CRC Press, 2009.
[158] K. Siddiqi, A. Shokoufandeh, S. J. Dickinson, and S. W. Zucker, “Shock graphs
and shape matching,” International Journal of Computer Vision, vol. 35, no. 1, pp.
13–32, 1999.
[159] K. Siddiqi, S. Bouix, A. Tannenbaum, and S. W. Zucker, “Hamilton-Jacobi skele-
tons,” International Journal of Computer Vision, vol. 48, no. 3, pp. 215–231,
2002.
[160] T. Sikora, “The MPEG-7 visual standard for content description - an overview,”
IEEE Transactions on Circuits and Systems for Video Technology, vol. 11, no. 6,
pp. 696–702, 2001.
118
[161] F. Soddy, “The kiss precise,” Nature, vol. 137, p. 1021, 1936.
[162] P. Soille, Morphological image analysis: principles and applications. Springer,
2004.
[163] P. G. Spain, “The Fermat point of a triangle,” Mathematics Magazine, vol. 69,
no. 2, pp. 131–133, 1996.
[164] V. Stelmashuk, “New approach to an underwater discharge simulation using elliptic
coordinates,” AIP Advances, vol. 10, no. 1, pp. 015 102.1–015 102.7, 2020.
[165] M. J. Sterling, Trigonometry for dummies. John Wiley & Sons, 2014.
[166] R. Strand, “Minimal paths by sum of distance transforms,” in Proceedings of the
International Conference on Discrete Geometry for Computer Imagery, 2016, pp.
349–358.
[167] R. Strzodka and A. C. Telea, “Generalized distance transforms and skeletons
in graphics hardware,” in Proceedings of the Joint Eurographics - IEEE TCVG
conference on Visualization, 2004, pp. 221–230.
[168] A. Sud, N. Govindaraju, and D. Manocha, “Interactive computation of discrete gen-
eralized Voronoi Diagrams using range culling,” in Proceedings of the International
Symposium on Voronoi Diagrams in Science and Engineering, 2005, pp. 1–10.
[169] K. Sugihara, M. Iri, H. Inagaki, and T. Imai, “Topology-oriented implementation –
an approach to robust geometric algorithms,” Algorithmica, vol. 27, no. 1, pp. 5–20,
2000.
[170] G. Sz.-Nagy, “Tschirnhaus´sche Flächen und Kurven,” Acta Mathematica
Academiae Scientiarum Hungarica, vol. 1, pp. 167–181, 1950.
[171] H. Talbot and B. C. Appleton, “Elliptical distance transforms and the object
splitting problem,” in Proceedings of the International Symposium on Mathematical
Morphology, 2002, pp. 229–240.
[172] T. Tayebi and H. F. Öztop, “Entropy production during natural convection of
hybrid nanofluid in an annular passage between horizontal confocal elliptic cylinders,”
International Journal of Mechanical Sciences, vol. 171, p. 105378, 2020.
[173] A. C. Telea and J. J. van Wijk, “An augmented fast marching method for computing
skeletons and centerlines,” in Proceedings of the Joint Eurographics-IEEE TCVG
Symposium on Visualization, 2002, pp. 251–259.
[174] E. Torricelli, “Opere di Evangelista Torricelli,” Edited by G. Vassura and G. Loria
and G. Montanari, vol. I/2, pp. 90–97, 1919.
[175] E. Torricelli, “Opere di Evangelista Torricelli,” Edited by G. Vassura and G. Loria
and G. Montanari, vol. III, p. 426–431, 1919.
119
[176] G. R. Veldkamp, “The isoperimetric point and the point(s) of equal detour in a
triangle,” The American Mathematical Monthly, vol. 92, no. 8, pp. 546–558, 1985.
[177] Cs. Vincze and Á. Nagy, “On the theory of generalized conics with applications
in geometric tomography,” Journal of Approximation Theory, vol. 164, no. 3, pp.
371–390, 2012.
[178] G. Voronoy, “Nouvelles applications des paramètres continus à la théorie des formes
quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs,”
Journal für die reine und angewandte Mathematik, vol. 134, pp. 198–287, 1908.
[179] J. Wang and M. Q.-H. Meng, “Optimal path planning using generalized Voronoi
graph and multiple potential functions,” IEEE Transactions on Industrial Elec-
tronics, vol. 67, no. 12, pp. 10 621–10 630, 2020.
[180] A. Weber, Über den Standort der Industrien. J. C. B. Mohr, 1922.
[181] G. O. Wesolowsky and R. F. Love, “Location of facilities with rectangular distances
among point and area destinations,” Naval Research Logistics Quarterly, vol. 18,
no. 1, pp. 83–90, 1971.
[182] A. P. Witkin, “Scale-space filtering,” in Readings in computer vision: issues,
problems, principles, and paradigms, 1987, pp. 329–332.
[183] H. Yagou, Y. Ohtake, and A. Belyaev, “Mesh smoothing via mean and median
filtering applied to face normals,” in Proceedings of the International Conference
on Geometric Modeling and Processing, 2002, pp. 124–131.
[184] M. Yang, K. Kpalma, and J. Ronsin, “Shape-based invariant feature extraction for
object recognition,” in Advances in Reasoning-Based Image Processing Intelligent
Systems: Conventional and Intelligent Paradigms. Springer, 2012, pp. 255–314.
[185] Y. Yang, J. Pan, and W. Wan, “Survey of optimal motion planning,” IET Cyber-
systems and Robotics, vol. 1, no. 1, pp. 13–19, 2020.
[186] C. K. Yap, “An O(N logN) algorithm for the Voronoi Diagram of a set of simple
curve segments,” Discrete & Computational Geometry, vol. 2, no. 4, pp. 365–393,
1987.
[187] C. K. Yap, “Towards exact geometric computation,” Computational Geometry,
vol. 7, no. 1-2, pp. 3–23, 1997.
[188] J. R. Young, Elements of Geometry: With Notes. Carey, Lea & Blanchard, 1833.
[189] D. Zhang and G. Lu, “Review of shape representation and description techniques,”
Pattern Recognition, vol. 37, no. 1, pp. 1–19, 2004.
[190] T. Y. Zhang and C. Y. Suen, “A fast parallel algorithm for thinning digital patterns,”
Communications of the ACM, vol. 27, no. 3, pp. 236–239, 1984.
120
Curriculum Vitae
❆②2②❧✉ ●❛❜❞✉❧❦❤❛❦♦✈❛✱ ❉✐♣❧✳✲■♥❣✳
❛②+②❧✉❅♣,✐♣✳*✉✇✐❡♥✳❛❝✳❛*
Education
2007 – 2012 Ufa State Aviation Technical University, Ufa, Russia
Diplom-Ingenieur in Computer Science
summa cum laude
1997 – 2007 Gymnasium №39, “UNESCO Associated School”, Ufa, Russia
Secondary Education
graduation with honors
2001 – 2005 Art School №2, Ufa, Russia
Secondary Education
graduation with honors
1997 – 2003 Music School №1, Ufa, Russia
Secondary Education
graduation with honors
Employment
11/2016 – 01/2021 Robert Bosch GmbH, Hildesheim, Germany
research, concept and algorithm development of the scalable sensor-
based maps in the area of automated driving
05/2016 – 11/2016 Software Quality Lab, Vienna, Austria
research and development of the prototypical system for Hardware-
in-the-Loop testing
11/2014 – 04/2015 CMORE Automotive, Böblingen, Germany
research and development in the project for automatic labeling of
the traffic signs
121
Reviewing Activities
2016, 2018,
2020, 2022
Visual observation and analysis of Vertebrate And Insect Behavior
Workshop (VAIB)
2019 International Joint Conference on Artificial Intelligence (IJCAI)
2017 IET Computer Vision Journal
Awards
10/2012 – 03/2016 Vienna PhD School of Informatics
grant for the doctoral studies at Vienna University of Technology
12/2011 – 03/2012 Erasmus Mundus scholarship
grant for Master studies at Vienna University of Technology
02/2011 – 06/2011 Erasmus Mundus scholarship
grant for Master studies at Vienna University of Technology
List of Publications
2021 Aysylu Gabdulkhakova, Walter G. Kropatsch:
Generalized conics with the sharp corners.
Iberoamerican Congress on Pattern Recognition, pages 419–429
2020 Aysylu Gabdulkhakova, Walter G. Kropatsch:
Generalized conics: properties and applications.
International Conference on Pattern Recognition, pp. 10728–10735
2019 Maximilian Langer, Aysylu Gabdulkhakova, Walter G. Kropatsch:
Non-centered Voronoi Skeletons.
Discrete Geometry for Computer Imagery - IAPR International
Conference, pp. 355–366
2018 Aysylu Gabdulkhakova, Walter G. Kropatsch:
Confocal Ellipse-based Distance and Confocal Elliptical Field for
polygonal shapes.
International Conference on Pattern Recognition, pp. 3025–3030
2018 Aysylu Gabdulkhakova, Maximilian Langer, Bernhard W. Langer,
Walter G. Kropatsch:
Line Voronoi Diagrams Using Elliptical Distances.
Structural, Syntactic, and Statistical Pattern Recognition - Joint
IAPR International Workshop, pp. 258–267
122