Extremal point queries with lines and line segments and related problems (Q2571215): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.comgeo.2005.03.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2033872228 / rank | |||
Normal rank |
Revision as of 20:22, 19 March 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