Paper Info

Title | ||
---|---|---|

Extremal point queries with lines and line segments and related problems |

Abstract | ||
---|---|---|

We address a number of extremal point query problems when P is a set of n points in R^d, d=3 a constant, including the computation of the farthest point from a query line and the computation of the farthest point from each of the lines spanned by the points in P. In R^3, we give a data structure of size O(n^1^+^@?), that can be constructed in O(n^1^+^@?) time and can report the farthest point of P from a query line segment in O(n^2^/^3^+^@?) time, where @?0 is an arbitrarily small constant. Applications of our results also include: (1) Sub-cubic time algorithms for fitting a polygonal chain through an indexed set of points in R^d, d=3 a constant, and (2) A sub-quadratic time and space algorithm that, given P and an anchor point q, computes the minimum (maximum) area triangle defined by q with P@?{q}. |

Year | DOI | Venue |
---|---|---|

2005 | 10.1016/j.comgeo.2005.03.002 | Comput. Geom. |

Keywords | Field | DocType |

area triangle,query,farthest point,computational geometry,algorithm,sub-cubic time algorithm,query line segment,extremal point query problem,size o,n point,query line,segment,related problem,anchor point q,sub-quadratic time,data structure,extreme point,indexation | Discrete mathematics,Line segment,Data structure,Combinatorics,Spacetime,Computational geometry,Polygonal chain,Mathematics,Computation | Journal |

Volume | Issue | ISSN |

32 | 3 | Computational Geometry: Theory and Applications |

Citations | PageRank | References |

3 | 0.50 | 25 |

Authors | ||

2 |

Authors (2 rows)

Cited by (3 rows)

References (25 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Ovidiu Daescu | 1 | 276 | 45.78 |

Robert Serfling | 2 | 22 | 3.80 |