# Proximity problems on line segments spanned by points

Title | Proximity problems on line segments spanned by points |

Publication Type | Journal Articles |

Year of Publication | 2006 |

Authors | Daescu O, Luo J, Mount D |

Journal | Computational Geometry |

Volume | 33 |

Issue | 3 |

Pagination | 115 - 129 |

Date Published | 2006/02// |

ISBN Number | 0925-7721 |

Keywords | Closest, Farthest, k closest lines, Minimum (maximum) area triangle, Proximity problem |

Abstract | Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O ( n log n ) time, O ( n ) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S ∖ { q } in optimal O ( n log n ) time and O ( n ) space. Finally, we give an O ( n log n ) time, O ( n ) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O ( n log n + k ) time and O ( n + k ) space. |

URL | http://www.sciencedirect.com/science/article/pii/S0925772105000805 |

DOI | 10.1016/j.comgeo.2005.08.007 |