Extremal point queries with lines and line segments and related problems (Q2571215): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q793457 |
Changed an Item |
||
Property / author | |||
Property / author: Robert J. Serfling / rank | |||
Normal rank |
Revision as of 02:46, 21 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Extremal point queries with lines and line segments and related problems |
scientific article |
Statements
Extremal point queries with lines and line segments and related problems (English)
0 references
1 November 2005
0 references
Let \(P\) be a set of \(n\) points in \(\mathbb R^d\), for some fixed \(d\geq 3\). The authors consider a number of extremal point query problems, 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 \(\mathbb R^3\), a data structure of size \(O(n^{1+\varepsilon})\) is given that can be constructed in time \(O(n^{1+\varepsilon})\) and can report the farthest point of \(P\) from a query line in \(O(n^{2/3+\varepsilon})\) time, where \(\varepsilon > 0\) is a constant that can be arbitrarily small. Applications include sub-cubic time algorithms for fitting a polygonal chain through an indexed set of points in \(\mathbb R^d\), \(d\geq 3\), and sub-quadratic time and space algorithms that computes the minimum or maximum area triangle defined by \(q\) with \(P\setminus\{q\}\), for a given set \(P\) and an anchor point \(q\).
0 references
algorithm
0 references
computational geometry
0 references
segment
0 references
query
0 references
farthest point
0 references