Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/7096
Title: | A note on determining the 3-dimensional convex hull of a set of points on a mesh of processors: Preliminary version | Authors: | Dehne F. Sack J. Stojmenović I. |
Issue Date: | 1-Jan-1988 | Journal: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Abstract: | © 1988, Springer-Verlag. This paper discusses the construction of the 3-dimensional convex hull for a set of n points stored on a √n × √n mesh of processors. Lu has shown that this problem can be solved in √n log n time if all points are located on a sphere. Here, we solve, in the same time-complexity, the 3-dimensional convex hull problem for arbitrary point sets. Furthermore, we observe a time/space trade off: if each processor is allocated O(log n) space then √n time is sufficient to determine the 3-dimensional convex hull. | URI: | https://open.uns.ac.rs/handle/123456789/7096 | ISBN: | 9783540194873 | ISSN: | 03029743 | DOI: | 10.1007/3-540-19487-8_18 |
Appears in Collections: | Naučne i umetničke publikacije |
Show full item record
SCOPUSTM
Citations
5
checked on May 3, 2024
Page view(s)
8
Last Week
5
5
Last month
0
0
checked on May 10, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.