# Computing a center-transversal line

Conference Paper

A center-transversal line for two finite point sets in R is a line with the property that any closed halfspace that contains it also contains at least one third of each point set. It is known that a center-transversal line always exists [12,24], but the best known algorithm for finding such a line takes roughly n time. We propose an algorithm that finds a center-transversal line in O(n κ (n)) worst-case time, for any ε>0, where κ(n) is the maximum complexity of a single level in an arrangement of n planes in R . With the current best upper bound κ(n) = O(n ) of [21], the running time is O(n ), for any ε>0. We also extend the concept of center-transversal line to that of bichromatic depth of lines in space, and give an algorithm that computes a deepest line exactly in time O(n κ (n)), and a linear-time approximation algorithm that computes, for any specified δ>0, a line whose depth is at least 1 − δ times the maximum depth. 3 12 1+ε 2 3 5/2 6+ε 1+ε 2

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Cabello, S; Sellarès, JA; Sharir, M

### Published Date

- January 1, 2006

### Published In

### Volume / Issue

- 4337 LNCS /

### Start / End Page

- 93 - 104

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### International Standard Book Number 13 (ISBN-13)

- 9783540499947

### Digital Object Identifier (DOI)

- 10.1007/11944836_11

### Citation Source

- Scopus