Standard

Parallel convex hull computation by generalised regular sampling. / Tiskin, Alexandre.

Euro-Par 2002. Parallel Processing: 8th International Euro-Par Conference Paderborn, Germany, August 27-30, 2002 Proceedings. Springer Nature, 2002. стр. 392-399 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 2400).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Tiskin, A 2002, Parallel convex hull computation by generalised regular sampling. в Euro-Par 2002. Parallel Processing: 8th International Euro-Par Conference Paderborn, Germany, August 27-30, 2002 Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 2400, Springer Nature, стр. 392-399. https://doi.org/10.1007/3-540-45706-2_52

APA

Tiskin, A. (2002). Parallel convex hull computation by generalised regular sampling. в Euro-Par 2002. Parallel Processing: 8th International Euro-Par Conference Paderborn, Germany, August 27-30, 2002 Proceedings (стр. 392-399). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 2400). Springer Nature. https://doi.org/10.1007/3-540-45706-2_52

Vancouver

Tiskin A. Parallel convex hull computation by generalised regular sampling. в Euro-Par 2002. Parallel Processing: 8th International Euro-Par Conference Paderborn, Germany, August 27-30, 2002 Proceedings. Springer Nature. 2002. стр. 392-399. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-45706-2_52

Author

Tiskin, Alexandre. / Parallel convex hull computation by generalised regular sampling. Euro-Par 2002. Parallel Processing: 8th International Euro-Par Conference Paderborn, Germany, August 27-30, 2002 Proceedings. Springer Nature, 2002. стр. 392-399 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{956e641e7cf44e008d6b09f37081c6db,
title = "Parallel convex hull computation by generalised regular sampling",
abstract = "The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We propose the first optimal deterministic BSP algorithm for computing the convex hull of a set of points in three-dimensional Euclidean space. Our algorithm is basedon known fundamental results from combinatorial geometry, concerning small-sized, efficiently constructible ϵ-nets and ϵ-approximations of a given point set. The algorithm generalises the technique of regular sampling, usedpreviously for sorting andt wodimensional convex hull computation. The cost of the simple algorithm is optimal only for extremely large inputs; we show how to reduce the requiredinput size by applying regular sampling in a multi-level fashion.",
author = "Alexandre Tiskin",
year = "2002",
month = jan,
day = "1",
doi = "10.1007/3-540-45706-2_52",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "392--399",
booktitle = "Euro-Par 2002. Parallel Processing",
address = "Germany",

}

RIS

TY - GEN

T1 - Parallel convex hull computation by generalised regular sampling

AU - Tiskin, Alexandre

PY - 2002/1/1

Y1 - 2002/1/1

N2 - The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We propose the first optimal deterministic BSP algorithm for computing the convex hull of a set of points in three-dimensional Euclidean space. Our algorithm is basedon known fundamental results from combinatorial geometry, concerning small-sized, efficiently constructible ϵ-nets and ϵ-approximations of a given point set. The algorithm generalises the technique of regular sampling, usedpreviously for sorting andt wodimensional convex hull computation. The cost of the simple algorithm is optimal only for extremely large inputs; we show how to reduce the requiredinput size by applying regular sampling in a multi-level fashion.

AB - The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We propose the first optimal deterministic BSP algorithm for computing the convex hull of a set of points in three-dimensional Euclidean space. Our algorithm is basedon known fundamental results from combinatorial geometry, concerning small-sized, efficiently constructible ϵ-nets and ϵ-approximations of a given point set. The algorithm generalises the technique of regular sampling, usedpreviously for sorting andt wodimensional convex hull computation. The cost of the simple algorithm is optimal only for extremely large inputs; we show how to reduce the requiredinput size by applying regular sampling in a multi-level fashion.

UR - http://www.scopus.com/inward/record.url?scp=84956864075&partnerID=8YFLogxK

U2 - 10.1007/3-540-45706-2_52

DO - 10.1007/3-540-45706-2_52

M3 - Conference contribution

AN - SCOPUS:84956864075

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 392

EP - 399

BT - Euro-Par 2002. Parallel Processing

PB - Springer Nature

ER -

ID: 127756745