VERTICAL DECOMPOSITION OF ARRANGEMENTS OF HYPERPLANES IN 4 DIMENSIONS

Authors
GUIBAS LJ HALPERIN D MATOUSEK J SHARIR M
Citation
Lj. Guibas et al., VERTICAL DECOMPOSITION OF ARRANGEMENTS OF HYPERPLANES IN 4 DIMENSIONS, Discrete & computational geometry, 14(2), 1995, pp. 113-122
Citations number
5
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
14
Issue
2
Year of publication
1995
Pages
113 - 122
Database
ISI
SICI code
0179-5376(1995)14:2<113:VDOAOH>2.0.ZU;2-C
Abstract
We show that, for any collection H of n hyperplanes in R(4), the combi natorial complexity of the vertical decomposition of the arrangement A (H) of H is O(n(4) log n). The proof relies on properties of superimpo sed convex subdivisions of 3-space, and we also derive some other resu lts concerning them.