摘要: We present a solution to the point location problem in arrangements of hyperplanes Ed with running time O(d5 log n) and space O(nd+?) for arbitrary ? > 0, where n is number hyperplanes. The main result d5 factor expression time. All previously known algorithms are exponential d or n. This leads nonuniform polynomial NP-complete problems.
core.ac.uk
acm.org
elsevier.com
sci-hub.se 参考文章(10)
P. K. Agarwal, A deterministic algorithm for partitioning arrangements of lines and its application symposium on computational geometry. pp. 11- 22 ,(1989) , 10.1145/73833.73835
Jiří Matoušek, Raimund Seidel, E. Welzl, How to net a lot with little: small ε-nets for disks and halfspaces symposium on computational geometry. pp. 16- 22 ,(1990) , 10.1145/98524.98530
Herbert Edelsbrunner, Algorithms in Combinatorial Geometry ,(1987)
K Clarkson, A probabilistic algorithm for the post office problem Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85. pp. 175- 184 ,(1985) , 10.1145/22145.22165
David Haussler, Emo Welzl, ɛ-nets and simplex range queries Discrete & Computational Geometry. ,vol. 2, pp. 127- 151 ,(1987) , 10.1007/BF02187876
K. L. Clarkson, Applications of random sampling in computational geometry, II symposium on computational geometry. ,vol. 4, pp. 1- 11 ,(1988) , 10.1145/73393.73394
David Dobkin, Richard J. Lipton, Multidimensional Searching Problems SIAM Journal on Computing. ,vol. 5, pp. 181- 186 ,(1976) , 10.1137/0205015
Friedhelm Meyer auf der Heide, On genuinely time bounded computations symposium on theoretical aspects of computer science. pp. 1- 16 ,(1989) , 10.1007/BFB0028969
David S Johnson, The NP-completeness column: An ongoing guide Journal of Algorithms. ,vol. 7, pp. 584- 601 ,(1986) , 10.1016/0196-6774(86)90020-9
Friedhelm Meyer auf der Heide, A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem Journal of the ACM. ,vol. 31, pp. 668- 676 ,(1984) , 10.1145/828.322450