Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers
dc.contributor.author | Miller, Russ | en_US |
dc.contributor.author | Cohen, Ed | en_US |
dc.contributor.author | Sarraf, Elias M. | en_US |
dc.contributor.author | Stout, Quentin F. | en_US |
dc.date.accessioned | 2006-09-08T19:09:52Z | |
dc.date.available | 2006-09-08T19:09:52Z | |
dc.date.issued | 1992-12 | en_US |
dc.identifier.citation | Cohen, Ed; Miller, Russ; Sarraf, Elias M.; Stout, Quentin F.; (1992). "Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers." Algorithmica 7(1): 51-75. <http://hdl.handle.net/2027.42/41352> | en_US |
dc.identifier.issn | 1432-0541 | en_US |
dc.identifier.issn | 0178-4617 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/41352 | |
dc.description.abstract | This paper gives hypercube algorithms for some simple problems involving geometric properties of sets of points. The properties considered emphasize aspects of convexity and domination. Efficient algorithms are given for both fine- and medium-grain hypercube computers, including a discussion of implementation, running times and results on an Intel iPSC hypercube, as well as theoretical results. For both serial and parallel computers, sorting plays an important role in geometric algorithms for determining simple properties, often being the dominant component of the running time. Since the time required to sort data on a hypercube computer is still not fully understood, the running times of some of our algorithms for unsorted data are not completely determined. For both the fine- and medium-grain models, we show that faster expected-case running time algorithms are possible for point sets generated randomly. Our algorithms are developed for sets of planar points, with several of them extending to sets of points in spaces of higher dimension. | en_US |
dc.format.extent | 1507560 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Springer-Verlag; Springer-Verlag New York Inc. | en_US |
dc.subject.other | Hypercube | en_US |
dc.subject.other | Software Engineering/Programming and Operating Systems | en_US |
dc.subject.other | Computer Systems Organization and Communication Networks | en_US |
dc.subject.other | Computer Science | en_US |
dc.subject.other | Computer Hardware | en_US |
dc.subject.other | Computational Geometry | en_US |
dc.subject.other | Domination | en_US |
dc.subject.other | Theory of Computation | en_US |
dc.subject.other | Data Structures, Cryptology and Information Theory | en_US |
dc.subject.other | Algorithm Analysis and Problem Complexity | en_US |
dc.subject.other | Convex Hull | en_US |
dc.subject.other | Parallel Algorithms | en_US |
dc.title | Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Philosophy | en_US |
dc.subject.hlbsecondlevel | Mathematics | en_US |
dc.subject.hlbtoplevel | Humanities | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Department of Electrical Engineering and Computer Science, University of Michigan, 48109, Ann Arbor, MI, USA | en_US |
dc.contributor.affiliationother | Amherst Systems Inc., 30 Wilson Road, 14221, Buffalo, NY, USA | en_US |
dc.contributor.affiliationother | Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA | en_US |
dc.contributor.affiliationother | Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/41352/1/453_2005_Article_BF01758751.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1007/BF01758751 | en_US |
dc.identifier.source | Algorithmica | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.