mdh.sePublications
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
Parallel computation of optimal enclosing balls by iterative orthant scan
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-1550-0994
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-6969-6793
2016 (English)In: Computers & graphics, ISSN 0097-8493, E-ISSN 1873-7684, Vol. 56, 1-10 p.Article in journal (Refereed) Published
Resource type
Text
Abstract [en]

We propose an algorithm for computing the exact minimum enclosing ball of large point sets in general dimensions. It aims to reduce the number of passes by retrieving a well-balanced set of outliers in each linear search through the input by decomposing the space into orthants. The experimental evidence indicates that the convergence rate in terms of the required number of linear passes is superior compared to previous exact methods, and substantially faster execution times are observed in dimensions d≤16. In the important three-dimensional case, the execution times indicate real-time performance. Furthermore, we show how the algorithm can be adapted for parallel execution on both CPU and GPU architectures using OpenMP, AVX, and CUDA. For large datasets, our CUDA solution is superior. For example, the benchmark results show that optimal bounding spheres for inputs with tens of millions of points can be computed in just a few milliseconds.

Place, publisher, year, edition, pages
2016. Vol. 56, 1-10 p.
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:mdh:diva-31461DOI: 10.1016/j.cag.2016.01.003ISI: 000375813900001Scopus ID: 2-s2.0-84962520463OAI: oai:DiVA.org:mdh-31461DiVA: diva2:922502
Available from: 2016-04-22 Created: 2016-04-22 Last updated: 2017-11-30Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Larsson, ThomasKällberg, Linus

Search in DiVA

By author/editor
Larsson, ThomasCapannini, GabrieleKällberg, Linus
By organisation
Embedded Systems
In the same journal
Computers & graphics
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 17 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