A note on searching line arrangements and applications

被引：8

作者：

Chen, Danny Z. ^{[1
]}

Wang, Haitao ^{[2
]}

机构：

[1] Univ Notre Dame, Dept Comp Sci & Engn, Notre Dame, IN 46556 USA

[2] Utah State Univ, Dept Comp Sci, Logan, UT 84322 USA

来源：

INFORMATION PROCESSING LETTERS | 2013年 / 113卷 / 14-16期

基金：

美国国家科学基金会;

关键词：

Line arrangement; Vertex searching; Points approximation; Computational geometry; Algorithm design; OPTIMAL SLOPE SELECTION; STEP-FUNCTION; ALGORITHMS; POINTS; APPROXIMATION;

D O I：

10.1016/j.ipl.2013.04.011

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study the problem of searching for a vertex with a desired property in the arrangement of a set of lines in the plane. We show that this problem can be solved efficiently by modifying (and simplifying) two slope selection algorithms without using parametric search. We apply this result to a points approximation problem and obtain an optimal solution for it without using parametric search. Since this line arrangement searching problem is quite natural, our result may find other applications as well. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：518 / 521

页数：4

共 21 条

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

AJTAI, M ;

KOMLOS, J ;

SZEMEREDI, E .

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

[2]

Alon Noga, 1992, The Probabilistic Method

[3] Efficient algorithms for optimization-based image segmentation [J].

Asano, T ;

Chen, DZ ;

Katoh, N ;

Tokuyama, T .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2001, 11 (02) :145-166

[4] Optimal slope selection via cuttings [J].

Bronnimann, H ;

Chazelle, B .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 10 (01) :23-29

[5] 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

[6]

Chen DZ, 2009, LECT NOTES COMPUT SC, V5878, P224, DOI 10.1007/978-3-642-10631-6_24

[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] SLOWING DOWN SORTING NETWORKS TO OBTAIN FASTER SORTING ALGORITHMS [J].

COLE, R .

JOURNAL OF THE ACM, 1987, 34 (01) :200-208

[9]

De Berg M., 2008, Computational Geometry: Algorithms and Applications, V17

[10]

Dobkin D., 1986, P 18 ANN ACM S THEOR, P387

← 1 2 3 →