Vi studerar skalbara parallella beräkningsgeometrialgoritmer för den grovkorniga multidatormodellen: p-processorer som löser ett problem på n dataobjekt, om varje processor har O( n p ) O(1) lokalt minne och alla processorer är anslutna via någon godtycklig sammankopplingsnätverk (t.ex. nät, hyperkub, fettträd). Vi presenterar O( Tsequential p + T s (n; p)) tid skalbara parallella algoritmer för flera beräkningsgeometri problem. T s (n; p) avser tiden för en global typ av operation. Våra resultat är oberoende av multidatorns sammankopplingsnät. Deras tidskomplexitet blir optimal när Tsequential p dominerar T s (n; p) eller när T s (n; p) är optimal. Detta är fallet för flera standardarkitekturer, inklusive maskor och hyperkuber, och ett brett spektrum av nyckeltal n p som inkluderar många av de för närvarande tillgängliga maskinkonvergenserna. Våra metoder har också några viktiga praktiska fördelar: För kommunikation mellan processorer använder de bara ett litet xed antal av en global routing operation, global typ, och alla andra programmering är i den sekventiella domänen. Dessutom använder våra algoritmer bara ett litet antal mycket stora meddelanden, vilket avsevärt minskar omkostnaderna för kommunikationsprotokollet mellan processorer. (Observera dock att vår tids komplexitet står för meddelandenas längd.) Experiment visar att våra metoder är enkla att implementera och ger bra timingresultat. En preliminär version av detta dokument har
I REF presenteras en algoritm för beräkning av knn-grafen för en 2-dimensionell Euclidean-punktuppsättning för grovkorniga multidatorer som körs i tid  på (n log n/p + t(n, p)), där n är antalet punkter i datamängden, p är antalet processorer, och t (n, p) är tiden för en global sort-operation.
Scalable parallel computational geometry for coarse grained multicomputers
{'venue': 'Int. J. Comput. Geometry Appl.', 'journal': None, 'mag_field_of_study': ['Computer Science']}