Vertical decompositions for triangles in 3-space

We prove that, for any constant ɛ>0, the complexity of the vertical decomposition of a set ofn triangles in three-dimensional space isO(n ^2+ɛ +K), whereK is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to beO(n ^2+ɛ ). These bounds are almost tight in the worst case. We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs inO(n ² logn+V logn) time, whereV is the complexity of the decomposition. The algorithm is reasonably simple (in particular, it tries to perform as much of the computation in two-dimensional spaces as possible) and thus is a good candidate for efficient implementations. The algorithm is extended to compute the vertical decomposition of arrangements ofn algebraic surface patches of constant maximum degree in three-dimensional space in timeO(nλ _q (n) logn +V logn), whereV is the combinatorial complexity of the vertical decomposition, λ _q (n) is a near-linear function related to Davenport-Schinzel sequences, andq is a constant that depends on the degree of the surface patches and their boundaries. We also present an algorithm with improved running time for the case of triangles which is, however, more complicated than the first algorithm. Mark de Berg was supported by the Dutch Organization for Scientific Research (N.W.O.), and by ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity). Leonidas Guibas was supported by NSF Grant CCR-9215219, by a grant from the Stanford SIMA Consortium, by NSF/ARPA Grant IRI-9306544, and by grants from the Digital Equipment, Mitsubishi, and Toshiba Corporations. Dan Halperin was supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. A preliminary version of this paper appeared inProc. 10th ACM Symposium on Computational Geometry, 1994, pp. 1–10.     

On the complexity of a single cell in certain arrangements of surfaces related to motion planning

We obtain near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in certain arrangements ofn surfaces in 3-space where the lower bound for this quantity is Ω(n ²) or slightly larger. We prove a theorem that identifies a collection of topological and combinatorial conditions for a set of surface patches in space, which make the complexity of a single cell in an arrangement induced by these surface patches near-quadratic. We apply this result to arrangements related to motion-planning problems of two types of robot systems with three degrees of freedom and also to a special type of arrangements of triangles in space. The complexity of the entire arrangement in each case that we study can be Θ(n ³) in the worst case, and our single-cell bounds are of the formO(n ² α(n)), O(n ² logn), orO(n ² α(n)logn). The only previously known similar bounds are for the considerably simpler arrangements of planes or of spheres in space, where the bounds are Θ(n) and Θ(n ²), respectively. For some of the arrangements that we study we derive near-quadratic-time algorithms to compute a single cell. A preliminary version of this paper has appeared inProc. 7th ACM Symposium on Computational Geometry, North Conway, NH, 1991, pp. 314–323.     

Primitive subspaces of Hopf algebras of finite depth

This research was partially supported by an NSERC operating grant, and by a NATO travel grant     

Photoenhancement of the photoconductivity (PC) of electron irradiated semiconducting diamond

The spectrum of the non-enhanced PC of electron irradiated semiconducting diamond extends from the UV towards the visible and near infrared. It's long wavelength tail was found in the present work to exhibit a well defined threshold shifted with temperature from about 1.5eV at 76 K to about 1.25 eV at 500 K. Pre-illumination in the “UV-band” produced an enhanced PC band with a temperature independent threshold at 1.08 0.03 eV. This photoenhanced band was found to be closely related to a thermally-simulated current peak (TSC) at 500 K with an activation energy of 0.50 eV excited by the pre-illumination in the UV-band. The prhotenhanced band was bleached out thermally with the exhaustion of the TSC peak below 600 K. Some of the characteristics of the photoenhanced band including the linear dependence of the square root of the PC on photon energy may suggest that internal photoemission of holes plays a role in the formation of this band.     

New bounds for lower envelopes in three dimensions,with applications to visibility in terrains

We consider the problem of bounding the complexity of the lower envelope ofn surface patches in 3-space, all algebraic of constant maximum degree, and bounded by algebraic arcs of constant maximum degree, with the additional property that the interiors of any triple of these surfaces intersect in at most two points. We show that the number of vertices on the lower envelope ofn such surface patches is , for some constantc depending on the shape and degree of the surface patches. We apply this result to obtain an upper bound on the combinatorial complexity of the “lower envelope” of the space of allrays in 3-space that lie above a given polyhedral terrainK withn edges. This envelope consists of all rays that touch the terrain (but otherwise lie above it). We show that the combinatorial complexity of this ray-envelope is for some constantc; in particular, there are at most that many rays that pass above the terrain and touch it in four edges. This bound, combined with the analysis of de Berget al. [4], gives an upper bound (which is almost tight in the worst case) on the number of topologically different orthographic views of such a terrain. Work on this paper by the first author has been supported by a Rothschild Postdoctoral Fellowship. Work on this paper by the second author has been supported by NSF Grant CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.