## 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.

Original language | British English |
---|---|

Pages (from-to) | 495-506 |

Number of pages | 12 |

Journal | International Journal of Computational Geometry and Applications |

Volume | 21 |

Issue number | 5 |

DOIs | |

State | Published - Oct 2011 |

## Keywords

- Bichromatic problems
- Counting
- Divide and conquer
- Enumeration
- Output-sensitive algorithms
- Simplices