Selecting distances in arrangements of hyperplanes spanned by points

作     者：Bespamyatnikh, Sergei Segal, Michael 

作者机构：Department of Computer Science University of Texas at Dallas Richardson TX 75083 United States Commun. Syst. Engineering Department Ben-Gurion University of the Negev Beer-Sheva 84105 Israel 

出 版 物：《Journal of Discrete Algorithms》 (J. Discrete Algorithms)

年 卷 期：2004年第2卷第3期

页      面：333-345页

核心收录：

学科分类：1202[管理学-工商管理] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

主　　题：Problem solving 

摘      要：In this paper we consider a problem of distance selection in the arrangement of hyperplanes induced by n given points. Given a set of n points in d-dimensional space and a number k, 1 &le k &le (d), determine the hyperplane that is spanned by d points and at distance ranked by k from the origin. For the planar case we present an O(n log2 n) runtime algorithm using parametric search partly different from the usual approach [N. Megiddo, J. ACM 30 (1983) 852]. We establish a connection between this problem in 3-d and the well-known 3 SUM problem using an auxiliary problem of counting the number of vertices in the arrangement of n planes that lie between two sheets of a hyperboloid. We show that the 3-d problem is almost 3SUM-hard and solve it by an O(n2 log2 n) runtime algorithm. We generalize these results to the d-dimensional (d ≥ 4) space and consider also a problem of enumerating distances. © 2003 Elsevier B.V. All rights reserved.