-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathTimings.html
120 lines (116 loc) · 5.28 KB
/
Timings.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
<!doctype html>
<html lang="en">
<head>
<!-- Required meta tags -->
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
<!-- Bootstrap CSS -->
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/css/bootstrap.min.css" integrity="sha384-Gn5384xqQ1aoWXA+058RXPxPg6fy4IWvTNh0E263XmFcJlSAwiGgFAW/dAiS6JXm" crossorigin="anonymous">
<!-- Optional JavaScript -->
<!-- jQuery first, then Popper.js, then Bootstrap JS -->
<script src="https://code.jquery.com/jquery-3.2.1.slim.min.js" integrity="sha384-KJ3o2DKtIkvYIK3UENzmM7KCkRr/rE9/Qpg6aAZGJwFDMVNA/GpGFF93hXpG5KkN" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.12.9/umd/popper.min.js" integrity="sha384-ApNbgh9B+Y1QKtv3Rn7W3mgPxhU9K/ScQsAP7hUibX39j7fakFPskvXusvfa0b4Q" crossorigin="anonymous"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/js/bootstrap.min.js" integrity="sha384-JZR6Spejh4U02d8jOt6vLEHfe/JQGiRRSQQxSfFWpi1MquVdAyjUar5+76PVCmYl" crossorigin="anonymous"></script>
<title>Hello, world!</title>
</head>
<body class="bg-dark" style="color:#EEEEEE">
<br>
<div class="container-fluid">
<div class="row justify-content-md-center">
<div class="col-md-auto">
<h1>Algorithm Comparison</h1>
</div>
</div>
<div class="row justify-content-md-center">
<div class="col-md-auto">
<p>This page contains the information about the Performance Comparison of the 3 convex hull algorithms</p>
</div>
</div>
<div class="row justify-content-md-center">
<h3>Performance <i>(in microseconds)</i></h3>
</div>
<div class="row justify-content-md-center">
<div class="col-md-auto">
<table class="table table-striped table-dark">
<thead>
<tr>
<th scope="col">Problem Size\Algorithm</th>
<th scope="col">Jarvis March O(n*h)</th>
<th scope="col">Graham Scan O(n*log<sub>2</sub>n)</th>
<th scope="col">Kirkpatrick Seidel O(n*log<sub>2</sub>h)</th>
<th scope="col">Average Number of hull points</th>
</tr>
</thead>
<tbody>
<tr>
<th scope="row">10</th>
<td>15.3</td>
<td>25.6</td>
<td>295.2</td>
<td>5</td>
</tr>
<tr>
<th scope="row">10<sup>2</sup></th>
<td>48.9</td>
<td>51.9</td>
<td>1260.3</td>
<td>9</td>
</tr>
<tr>
<th scope="row">10<sup>3</sup></th>
<td>419.2</td>
<td>480</td>
<td>11487.4</td>
<td>10</td>
</tr>
<tr>
<th scope="row">10<sup>4</sup></th>
<td>3883.6</td>
<td>4963.9</td>
<td>192884.6</td>
<td>10</td>
</tr>
<tr>
<th scope="row">10<sup>5</sup></th>
<td>63777.2</td>
<td>56203.9</td>
<td>11512395.2</td>
<td>17</td>
</tr>
<tr>
<th scope="row">10<sup>6</sup></th>
<td>590412.8</td>
<td>635221.6</td>
<td>1001285888.4</td>
<td>17</td>
</tr>
</tbody>
</table>
</div>
</div>
<br>
<div class="row justify-content-md-center">
<h3>Plots</h3>
</div>
<div class="row justify-content-md-center">
<img src="Graham Scan.png" alt="">
</div>
<hr>
<div class="row justify-content-md-center">
<img src="Jarvis March.png" alt="">
</div>
<hr>
<div class="row justify-content-md-center">
<img src="Kirkpatrick Seidel.png" alt="">
</div>
<hr>
<div class="row justify-content-md-center">
<h3>Conclusions</h3>
</div>
<div class="row justify-content-md-center">
<p>Jarvis march performs better on an average, however, the difference between them is not significant, in the sense that they both run in the same order of time.
However, Kirkpartik-Sidel does not seem to scale up to that factor due to the fact that the use of vectors is not efficient due to the large number of memory operations. </p>
</div>
</div>
</body>
</html>