-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathimplementation.html
191 lines (178 loc) · 10 KB
/
implementation.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
<!DOCTYPE HTML>
<html>
<head>
<title>Order Types</title>
<meta name="description" content="website description"/>
<meta name="keywords" content="website keywords, website keywords"/>
<meta http-equiv="content-type" content="text/html; charset=UTF-8"/>
<link rel="stylesheet" type="text/css" href="/style/style.css" title="style"/>
<script src="https://code.jquery.com/jquery-3.5.1.min.js"
integrity="sha256-9/aliU8dGd2tb6OSsuzixeV4y/faTqgFtohetphbbj0=" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script>
</head>
<body>
<div id="main">
<div id="header">
<div id="menubar">
<ul id="menu">
<li><a href="/index.html">Home</a></li>
<li><a href="/tutorial.html">Tutorial</a></li>
<li><a href="/glossary.html">Glossary</a></li>
<li><a href="/demo.html">Interactive Demo</a></li>
<li class="selected"><a href="/implementation.html">implementation details</a></li>
</ul>
</div>
</div>
<div id="site_content">
<div id="content">
<h1><b>Implementation details of key algorithms</b></h1>
<p>On this page we will go over the implementation details of the key algorithms of the program.</p>
<h2>Natural λ-matrix</h2>
<p>
J. E. Goodman and R. Pollack proved the equivalence of λ-matrices and Order Type of a point
set in [Multidimensional sorting, 1983] and described an algorithm to compute the λ-matrix of
a labelled point set.
</p>
<p>
To uniquely identify an Order Type, [Aichholtzer et al., 2001] used the λ-matrix of smallest
lexicographical order, the natural λ-matrix. They used this to sort their exhaustive database
of Order Types. To be able to compare the Order Types of two
point sets an algorithm to compute the natural λ-matrix is needed. Aichholtzer describes one
such algorithm in the <a
href="http://conferences2.imfm.si/conferenceDisplay.py/getPic?picId=36&confId=12">slides</a>
of a presentation at a conference.
</p>
<fig>
<img src="/images/implementation/slide.png" width=100%;
alt="slide from Aichholtzer's presentation at Portoroz, Slovenia 2012">
<figcaption style="text-align: center;">Slide from Aichholtzer's presentation at CSD6 Portoroz,
Slovenia in 2012
</figcaption>
</fig>
<br>
<p>
The idea is the consider each point on the convex hull in turn as a pivot for a clockwise radial sort in
order to determine a labelling of the points. For each of these labellings, the λ-matrix is
computed. A λ-matrix M is an n*n matrix (where n is the size of the point set) with each entry
M(i, j) containing the number of points that lie on the left of the ordered line through point i and
point j. In the end, only the matrix with smallest lexicographical value is kept as the natural
λ-matrix.
</p>
<pre class="prettyprint lang-js" style="margin-top: 10px;">
function minLambdaMatrixString(pointSet) {
let convexHull = grahamScan(pointSet);
let minMatrix = undefined;
// try each point on convex hull as pivot
for (let pivotId in convexHull) {
let tmpMatrix = "";
let pivotPoint = convexHull[pivotId];
let ordered = orderRadially(pointSet, pivotPoint, true);
for (let i in ordered) {
for (let j in ordered) {
tmpMatrix += nbPointsLeftOf(ordered[i], ordered[j], ordered);
}
}
if (minMatrix === undefined || tmpMatrix.localeCompare(minMatrix) < 0) {
minMatrix = tmpMatrix;
}
}
return minMatrix;
}</pre>
<p>
We will now perform a quick analysis of the complexity of the algorithm presented here-above:
</p>
<ul>
<li>
The complexity of computing the convex hull of n points is the complexity of the Graham Scan
algorithm, hence <i>O(n log(n))</i>.
</li>
<li>
Sorting the points radially around another uses the classical merge sort algorithm, hence it has a
complexity of <i>O(n log(n))</i>.
</li>
<li>
Computing the λ-matrix, once the points' order is set, has a complexity which is cubic in
number of points. This is because for each ordered pair of points we need to iterate over all the
other points and verify in which half-plane they are. Overall, computing this step takes
<i>O(n³)</i>.
</li>
<li>
Because the sorting step is dominated by the computation of the λ-matrix, the total
complexity
of the algorithm is <i>O(k n³)</i>, where k is the number of points on the convex hull.
</li>
</ul>
<h2>Binary Search equivalent point set</h2>
<p>
The order types database is exhaustive for the considered number of points, hence a guarantee is
provided that all the possible sets of points drawn by the user, containing between 3 and 9 points, have
a corresponding sets of points in the dataset. The entries of this dataset are ordered lexicographically
based on their natural λ - matrix, making it possible to search the database using a simple and
efficient binary search algortihm. In such a binary search algorithm, the half of the elements to be
searched is determined by comparing the natural λ matrix of the middle element with the one of
drawn points and the algorithm is called recursively on the newly determined half or it stops if the
middle set of points is the desired one.
</p>
<pre class="prettyprint lang-js" style="margin-top: 10px;">
function binSearchOt(nbPoints, inputLambdaMatrix) {
let arr = readOtypeDataset(nbPoints);
let entrySize = nbPoints * 2; // n points of 2 coordinates
let lastEntryIndex = (arr.length / entrySize) - 1;
return _recBinSearchOt(arr, 0, lastEntryIndex, nbPoints, inputLambdaMatrix);
}
function _recBinSearchOt(arr, lo, hi, nbPoints, inputLambdaMatrix) {
let midPoint = Math.floor((lo + hi) / 2);
let pointSet = readPointSet(arr, midPoint, nbPoints);
let midPointMatrix = minLambdaMatrixString(pointSet);
let res = midPointMatrix.localeCompare(inputLambdaMatrix);
if (lo === hi) {
if (res === 0) {
return { points: pointSet, index: lo };
} else {
return undefined;
}
}
if (res === 0) {
return { points: pointSet, index: midPoint };
} else if (res < 0) {
return _recBinSearchOt(arr, midPoint + 1, hi, nbPoints, inputLambdaMatrix);
} else {
return _recBinSearchOt(arr, lo, midPoint, nbPoints, inputLambdaMatrix);
}
}
</pre>
<br>
<h2>Load point set from the database files</h2>
<p>
The files of the exhaustive Order Type database contain coordinates of points encoded on 8 or 16
bits. Multibyte coordinates are stored in Big Endian format. To load the point set at a given entry
index we need to create points, in order, parsing the numbers in the file as their coordinates.
An array is used to contain the coordinates instead of the raw file.
</p>
<p>
In order to directly access a point set corresponding to a specific Order Type, the offset inside
the array needs to be computed first (the use of Uint8Array or Uint16Array hides the size of the
underlying coordinates, simplifying offset computation). The position of the first point is thus
the index of the set times the size of an entry (i.e. number of points times 2 coordinates).
</p>
<br>
<h2>Implementation choices</h2>
<p>
Because of the computational requirements imposed by the application functions, we decided to perform
the computation on the client side, rather then the server. A second argument for this decision was
the intent of keeping the communication with the server and the server application itself to a minimum.
Nevertheless, the implementation is written in JavaScript, a full-stack language, hence it can be easily
ported to the server side or in a local application, without requiring extensive modifications.
</p>
<p>
Our second decision is with respect to dataset files used by our application: given the exponential
increase in file size, we restricted the application to 9 points. This restriction does not affect the
functionality, nor the scalability of the application when considering the 10 points dataset also. A
second argument for this decision is the fact that the goal of this demo is to let the users familiarise
themselves with the concept of order types and explore the database provided by [Aichholtzer et al.,
2001], hence limiting the application to just 9 points does not impede on this goal.
</p>
</div>
</div>
</div>
</body>