Abstract We propose a method to simultaneously decompose a 3D object into power diagram cells and to integrate given functions in each of the obtained simple regions. We offer a novel, highly parallel algorithm that lends itself to an efficient GPU implementation. It is optimized for algorithms that need to compute many decompositions, for instance, centroidal Voronoi tesselation algorithms and incompressible fluid dynamics simulations. We propose an efficient solution that directly evaluates the integrals over every cell without computing the power diagram explicitly and without intersecting it with a tetrahedralization of the domain. Most computations are performed on the fly, without storing the power diagram. We manipulate a triangulation of the boundary of the domain (instead of tetrahedralizing the domain) to speed up the process. Moreover, the cells are treated independently one from another, making it possible to trivially scale up on a parallel architecture. Despite recent Voronoi diagram generation methods optimized for the GPU, computing integrals over restricted power diagrams still poses significant challenges; the restriction to a complex simulation domain is difficult and likely to be slow. It is not trivial to determine when a cell of a power diagram is completely computed, and the resulting integrals (e.g. the weighted Laplacian operator matrix) do not fit into fast (shared) GPU memory. We address all these issues and boost the performance of the state‐of‐the‐art algorithms by a factor 2 to 3 for (unrestricted) Voronoi diagrams and a ×50 speed‐up with respect to CPU implementations for restricted power diagrams. An essential ingredient to achieve this is our new scheduling strategy that allows us to treat each Voronoi/power diagram cell with optimal settings and to benefit from the fast memory.

Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We focus on the expected number of color comparisons when the c n colorings are equally probable. We analyze an obvious algorithm, showing that its expected performance is c 2 + c − 2/2 c n − O ( c 2 ), with variance Θ( c 2 n ). We present and analyze an algorithm for the case c = 3 colors whose average complexity on the 3 n equally probable inputs is 7083/5425 n + O (√ n ) = 1.3056… n + O (√ n ), substantially better than the expected complexity 5/3 n + O (1) = 1.6666… n + O (1) of the obvious algorithm. We describe a similar algorithm for c =4 colors whose average complexity on the 4 n equally probable inputs is 761311/402850 n + O (log n ) = 1.8898… n + O (log n ), substantially better than the expected complexity 9/4 n + O (1) = 2.25 n + O (1) of the obvious algorithm.

Many algorithms in texture synthesis, nonphotorealistic rendering (hatching), or remeshing require to define the orientation of some features (texture, hatches, or edges) at each point of a surface. In early works, tangent vector (or tensor) fields were used to define the orientation of these features. Extrapolating and smoothing such fields is usually performed by minimizing an energy composed of a smoothness term and of a data fitting term. More recently, dedicated structures ( N -RoSy and N -symmetry direction fields ) were introduced in order to unify the manipulation of these fields, and provide control over the field's topology (singularities). On the one hand, controlling the topology makes it possible to have few singularities, even in the presence of high frequencies (fine details) in the surface geometry. On the other hand, the user has to explicitly specify all singularities, which can be a tedious task. It would be better to let them emerge naturally from the direction extrapolation and smoothing. This article introduces an intermediate representation that still allows the intuitive design operations such as smoothing and directional constraints, but restates the objective function in a way that avoids the singularities yielded by smaller geometric details. The resulting design tool is intuitive, simple, and allows to create fields with simple topology, even in the presence of high geometric frequencies. The generated field can be used to steer global parameterization methods (e.g., QuadCover).

Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We prove that ( c − 1)( n − c )/2 color comparisons are necessary in the worst case to determine the plurality color and give an algorithm requiring (0.775 c + 5.9) n + O ( c 2 ) color comparisons for c ≥ 9.

Given a set of n elements, each of which is colored one of c ≥ 2 colors, we have to determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We derive lower bounds for the expected number of color comparisons when the c n colorings are equally probable. We prove a general lower bound of c /3 n − O (√ n ) for c ≥ 2; we prove the stronger particular bounds of 7/6 n − O (√ n ) for c = 3, 54/35 n − O (√ n ) for c = 4, 607/315 n − O (√ n ) for c = 5, 1592/693 n − O (√ n ) for c = 6, 7985/3003 n − O (√ n ) for c = 7, and 19402/6435 n − O (√ n ) for c = 8.

In this article, we introduce a general-purpose method for computing radiosity on scenes made of parametric surfaces with arbitrary trimming curves. In contrast with past approaches that require a tessellation of the input surfaces (be it made up of triangles or patches with simple trimming curves) or some form of geometric approximation, our method takes full advantage of the rich and compact mathematical representation of objects. At its core lies the virtual mesh , an abstraction of the input geometry that allows complex shapes to be illuminated as if they were simple primitives. The virtual mesh is a collection of normalized square domains to which the input surfaces are mapped while preserving their energy properties. Radiosity values are then computed on these supports before being lifted back to the original surfaces. To demonstrate the power of our method, we describe a high-order wavelet radiosity implementation that uses the virtual mesh. Examples of objects and environments, designed for interactive applications or virtual reality, are presented. They prove that, by exactly integrating curved surfaces in the resolution process, the virtual mesh allows complex scenes to be rendered more quickly, more accurately, and much more naturally than with previously known methods.

Since wavelets were introduced in the radiosity algorithm 5, surprisingly little research has been devoted to higher order wavelets and their use in radiosity algorithms. A previous study 13 has shown that wavelet radiosity, and especially higher order wavelet radiosity was not bringing significant improvements over hierarchical radiosity and was having a very important extra memory cost, thus prohibiting any effective computation. In this paper, we present a new implementation of wavelets in the radiosity algorithm, that is substantially different from previous implementations in several key areas (refinement oracle, link storage, resolution algorithm). We show that, with this implementation, higher order wavelets are actually bringing an improvement over standard hierarchical radiosity and lower order wavelets.

Given a set of n elements each of which is either red or blue, it is known that in the worst case $n-\nu(n)$ pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where $\nu(n)$ is the number of 1-bits in the binary representation of n. We prove that $\frac{2n}{3} - \sqrt\frac{8n}{9\pi} + O(\log n)$ such comparisons are necessary and sufficient in the average case.

Bounds are obtained for the solution to the divide-and-conquer recurrence \[ M( n ) = \max \limits_{k_1 + \cdots + k_p = n} ( M( k_1 ) + M( k_2 ) + \cdots + M( k_p )+ \min ( f ( k_1 ), \cdots ,f ( k_p ) ) ), \] for nondecreasing functions f. Similar bounds are found for the recurrence with “min” replaced by “sum-of-all-but-the-max.” Such recurrences appear in the analysis of various algorithms. The bounds follow from analyses of partition trees.

Given a lion and a man, their initial positions, and restrictions on their ranges and speeds, how quickly can the lion get within a given distance from the man? We consider the case in which the lion and man are restricted to the interior of a circle and each is limited to the same speed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.