Optimal slope selection via cuttings

被引：23

作者：

Bronnimann, H

Chazelle, B

机构：

[1] INRIA Sophia Antipolis, F-06902 Sophia Antipolis, France

[2] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1998年 / 10卷 / 01期

关键词：

deterministic optimal algorithm; arrangements; sorting;

D O I：

10.1016/S0925-7721(97)00025-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We give an optimal deterministic O(n log n)-time algorithm for slope selection. The algorithm borrows from the optimal solution given in (Cole et al., 1989) but avoids the complicated machinery of the AKS sorting network and parametric searching. This is achieved by redesigning and refining the O(n log(2) n)-time algorithm of Chazelle et al, (1993) with the help of additional approximation tools. (C) 1998 Elsevier Science B.V.

引用

收藏

页码：23 / 29

页数：7

相关论文

共 14 条

[1] SORTING IN C LOG N PARALLEL STEPS [J].

AJTAI, M ;

KOMLOS, J ;

SZEMEREDI, E .

COMBINATORICA, 1983, 3 (01) :1-19

[2]

Bronnimann H., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P400, DOI 10.1109/SFCS.1993.366847

[3]

BRONNIMANN H, IN PRESS SIAM J COMP

[4] DIAMETER, WIDTH, CLOSEST LINE PAIR, AND PARAMETRIC SEARCHING [J].

CHAZELLE, B ;

EDELSBRUNNER, H ;

GUIBAS, L ;

SHARIR, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 10 (02) :183-196

[5] CUTTING HYPERPLANES FOR DIVIDE-AND-CONQUER [J].

CHAZELLE, B .

DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (02) :145-158

[6]

CHAZELLE B, 1993, PROCEEDINGS OF THE FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P281

[7] AN OPTIMAL-TIME ALGORITHM FOR SLOPE SELECTION [J].

COLE, R ;

SALOWE, JS ;

STEIGER, WL ;

SZEMEREDI, E .

SIAM JOURNAL ON COMPUTING, 1989, 18 (04) :792-810

[8] A RANDOMIZED ALGORITHM FOR SLOPE SELECTION [J].

Dillencourt, Michael B. ;

Mount, David M. ;

Netanyahu, Nathan S. .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1992, 2 (01) :1-27

[9] SORTING X + Y [J].

HARPER, LH ;

PAYNE, TH ;

SAVAGE, JE ;

STRAUS, E .

COMMUNICATIONS OF THE ACM, 1975, 18 (06) :347-349

[10] OPTIMAL SLOPE SELECTION VIA EXPANDERS [J].

KATZ, MJ ;

SHARIR, M .

INFORMATION PROCESSING LETTERS, 1993, 47 (03) :115-122