|
|||||
|
|
Vertical decomposition of arrangements of hyperplanes in four dimensions |
|
| Authors: | L J Guibas D Halperin J Matoušek M Sharir |
| Institution: | 1. Department of Computer Science, Stanford University, 94305, Stanford, CA, USA 2. Robotics Laboratory, Department of Computer Science, Stanford University, 94305, Stanford, CA, USA 3. Deparmtent of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic 4. Institut für Informatik, Freie Universit?t Berlin, Arnimalle 2-6, D-14195, Berlin, Germany 5. School of Mathematical Sciences, Tel Aviv University, 69978, Tel Aviv, Israel 6. Courant Institute of Mathematical Sciences, New York University, 10012, New York, NY, USA |
| Abstract: | We show that, for any collection ℋ ofn hyperplanes in ℜ4, the combinatorial complexity of thevertical decomposition of the arrangementA(ℋ) of ℋ isO(n 4 logn). The proof relies on properties of superimposed convex subdivisions of 3-space, and we also derive some other results concerning them. Work on this paper by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Leonidas Guibas was also supported by National Science Foundation Grant CCR-9215219. Work by Micha Sharir was also supported by National Science Foundation Grant CCR-91-22103, and by grants from the G.I.F.—the German Isreali Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. Work by Jiří Matouŝek was done while he was visiting Tel Aviv University, and its was partially supported by a Humboldt Research Fellowship. Work on this paper by Dan Halperin was carried out while he was at Tel Aviv University. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |