### Abstract

Let B be a set of n unit balls in ℝ^{3}. We show that the combinatorial complexity of the space of lines in ℝ^{3} that avoid all the balls of B is O(n^{3+ε}), for any ε > 0. This result has connections to problems in visibility, ray shooting, motion planning and geometric optimization.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) |

Pages | 36-45 |

Number of pages | 10 |

State | Published - 2004 |

Event | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004 |

### Other

Other | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) |
---|---|

Country | United States |

City | Brooklyn, NY |

Period | 6/9/04 → 6/11/04 |

### Keywords

- Combinatorial complexity
- Lines in space
- Visibility

### ASJC Scopus subject areas

- Software
- Geometry and Topology
- Safety, Risk, Reliability and Quality
- Chemical Health and Safety

## Fingerprint Dive into the research topics of 'On lines avoiding unit balls in three dimensions'. Together they form a unique fingerprint.

## Cite this

Agarwal, P. K., Aronov, B., Koltun, V., & Sharir, M. (2004). On lines avoiding unit balls in three dimensions. In

*Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)*(pp. 36-45)