Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
CPU Performance Evaluation for 2D Voronoi Tessellation
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.
2019 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Voronoi tessellation can be used within a couple of different fields. Some of these fields include healthcare, construction and urban planning. Since Voronoi tessellations are used in multiple fields, it is motivated to know the strengths and weaknesses of the algorithms used to generate them, in terms of their efficiency.

The objectives of this thesis are to compare two CPU algorithm implementations for Voronoi tessellation in regards to execution time and see which of the two is the most efficient. The algorithms compared are The Bowyer-Watson algorithm and Fortunes algorithm.

The Fortunes algorithm used in the research is based upon a pre-existing Fortunes implementation while the Bowyer-Watson implementation was specifically made for this research. Their differences in efficiency were determined by measuring their execution times and comparing them. This was done in an iterative manner, where for each iteration, the amount of data to be computed was continuously increased.

The results show that Fortunes algorithm is more efficient on the CPU without using any acceleration techniques for any of the algorithms. It took 70 milliseconds for the Bowyer-Watson method to calculate 3000 input points while Fortunes method took 12 milliseconds under the same conditions.

As a conclusion, Fortunes algorithm was more efficient due to the Bowyer-Watson algorithm doing unnecessary calculations. These calculations include checking all the triangles for every new point added. A suggestion for improving the speed of this algorithm would be to use a nearest neighbour search technique when searching through triangles.

Place, publisher, year, edition, pages
2019. , p. 30
Keywords [en]
Voronoi tessellation, CPU performance, Fortunes algorithm, The Bowyer-Watson algorithm
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:bth-18259OAI: oai:DiVA.org:bth-18259DiVA, id: diva2:1333680
Subject / course
DV1478 Bachelor Thesis in Computer Science
Educational program
DVGSP Game Programming
Supervisors
Examiners
Available from: 2019-07-26 Created: 2019-07-01 Last updated: 2019-07-26Bibliographically approved

Open Access in DiVA

BTH2019EklundOlsson(2775 kB)18 downloads
File information
File name FULLTEXT02.pdfFile size 2775 kBChecksum SHA-512
90534cb15c1905ba573cdbe518c591b60e8ee536b1c98f359b81ca72686722c9023c92f4fac26bfd1b8b39f27272eb18f3a118b61b93396eb06331b928d1e6b6
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Olsson, VictorEklund, Viktor
By organisation
Department of Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 18 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 30 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf