POINT LOCATION AMONG HYPERPLANES AND UNIDIRECTIONAL RAY-SHOOTING

被引：13

作者：

CHAZELLE, B ^{[1
]}

FRIEDMAN, J ^{[1
]}

机构：

[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1994年 / 4卷 / 02期

基金：

美国国家科学基金会;

关键词：

POINT LOCATION; RAY-SHOOTING; MULTIDIMENSIONAL SEARCHING;

D O I：

10.1016/0925-7721(94)90009-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present an algorithm for locating a query point q in an arrangement of n hyperplanes in R(d). The size of the data structure is O(n(d)) and the time to answer any query is O(log n). Unlike previous data structures, our solution will also report, in addition to the face of the arrangement that contains q, the first hyperplane that is hit (if any) by shooting the point q in some fixed direction. Actually, if this ray-shooting capability is all that is needed, or if one only desires to know a single vertex of the face enclosing q, then the storage can be reduced to O(n(d)/(log n) inverted right perpendicular d/2 inverted left perpendicular -epsilon), for any fixed epsilon > 0.

引用

页码：53 / 62

页数：10

共 12 条

[1]

[Anonymous], 1987, EATCS MONOGRAPHS THE

[2]

ARONOV B, 1991, 7TH P ACM S COMP GEO, P307

[3] A DETERMINISTIC VIEW OF RANDOM SAMPLING AND ITS USE IN GEOMETRY [J].