Name
Abstract | ||
|---|---|---|
We show that finding the simplices containing a fixed given point among those defined on a set of n points can be done in O(n + k) time for the two-dimensional case, and in O(n(2) + k) time for the three-dimensional case, where k is the number of these simplices.As a byproduct, we give an alternative (to the algorithm in Ref. 4) O(n log r) algorithm that finds the red-blue boundary for n bichromatic points on the line, where r is the size of this boundary. Another byproduct is an O(n(2) + t) algorithm that finds the intersections of line segments having two red endpoints with those having two blue endpoints defined on a set of n bichromatic points in the plane, where t is the number of these intersections. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1142/S0218195911003779 | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | DocType | Volume |
Enumeration, counting, simplices, output-sensitive algorithms, bichromatic problems, divide and conquer | Journal | 21 |
Issue | ISSN | Citations |
5 | 0218-1959 | 2 |
PageRank | References | Authors |
0.40 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Khaled M. Elbassioni | 1 | 287 | 42.96 |
| Amr Elmasry | 2 | 259 | 34.53 |
| Kazuhisa Makino | 3 | 1088 | 102.74 |