Related Experiment Video
Updated: Jun 5, 2026
11:24
Evaporation-reducing Culture Condition Increases the Reproducibility of Multicellular Spheroid Formation in Microtiter Plates
Published on: March 7, 2017
GPU-assisted computation of centroidal Voronoi tessellation
Guodong Rong1, Yang Liu, Wenping Wang
1Department of Computer Science, University of Texas at Dallas, 800 W. Campbell Road, Richardson, TX 75083, USA. guodongrong@utdallas.edu
IEEE Transactions on Visualization and Computer Graphics
|January 15, 2011
Summary
This study accelerates Centroidal Voronoi Tessellations (CVT) computation using graphics processing units (GPUs). GPU implementation of Lloyd's and L-BFGS methods offers significant speedups for 2D planes and surfaces.
Area of Science:
- Computational Geometry
- Scientific Computing
- Computer Graphics
Background:
- Centroidal Voronoi Tessellations (CVT) are essential in computational science.
- Lloyd's method and L-BFGS are common but CPU-bound CVT algorithms.
- Existing methods are often too slow for large-scale applications.
Purpose of the Study:
- To accelerate CVT computation using GPU hardware.
- To adapt CVT algorithms for both 2D planes and complex surfaces.
- To demonstrate the performance benefits of GPU acceleration.
Main Methods:
- Implemented Lloyd's and L-BFGS methods on GPUs.
- Utilized geometry images for surface-based CVT.
- Developed a parallel regional reduction technique for integral evaluation on GPUs.
Main Results:
- Achieved significant speedups for GPU-based CVT compared to CPU methods.
- Demonstrated effective CVT computation on 2D planes and surfaces using GPUs.
- Validated the efficiency of the parallel regional reduction technique.
Conclusions:
- GPU acceleration dramatically improves CVT computation speed.
- The proposed methods enable efficient CVT on complex geometric surfaces.
- This work facilitates practical applications requiring fast CVT solutions.
Related Concept Videos
01:24Area Computation by the Alternative Coordinate Method
The alternative coordinate method, also known as the Shoelace Formula, is a technique for determining the area of a traverse using Cartesian coordinates. This method relies on the sequential arrangement of x and y coordinates for each point of the shape, ensuring accuracy and ease of application.In this approach, each corner's x and y coordinates are listed as fractions, with the x-coordinate as the numerator and the y-coordinate as the denominator. These coordinates are arranged sequentially...
01:16Centroid for the Paraboloid of Revolution
The paraboloid of revolution is an axially symmetric surface generated by rotating a parabola around its axis. This shape has several applications in mechanical engineering due to its advantageous structural properties, such as strength against stress concentration points and rotational symmetry.
The centroid for the paraboloid of revolution is the point where all the mass of the paraboloid is concentrated. This centroid is important for engineering applications, as it determines how forces are...
The centroid for the paraboloid of revolution is the point where all the mass of the paraboloid is concentrated. This centroid is important for engineering applications, as it determines how forces are...
01:16Centroid of a Body
The centroid is an important concept in engineering, physics, and mechanics. It is the geometric center of a body. It always lies within the body except in cases with holes or cavities. When the material that a body is composed of is uniform or homogeneous, the centroid coincides with its center of mass or the center of gravity.
For a homogeneous body with constant density, the centroid can usually be found using equations representing a balance of the moments of the body's volume. If the...
For a homogeneous body with constant density, the centroid can usually be found using equations representing a balance of the moments of the body's volume. If the...
01:03Centroid of a Body: Problem Solving
The centroid of a body is a crucial concept in engineering and physics. Finding the centroid of a body can help determine its stability, its balance point, and even its design. In this context, consider a thin wire bent in the form of a quarter circular arc. Polar coordinates are used to calculate the centroid. The wire is first divided into small differential elements of a length equal to the radius multiplied by the differential angle.
The x-coordinates and y-coordinates of each element's...
The x-coordinates and y-coordinates of each element's...
01:30Applications of Integration to Find Centers of Mass
Rotational equilibrium provides a natural framework for defining the center of mass of a system. For a plank balanced on a pivot with two unequal masses, equilibrium is achieved when the net torque about the pivot is zero. Torque is defined as the product of a force and its perpendicular distance from the pivot. When the torques due to all forces cancel, the pivot coincides with the center of mass of the system.For a system composed of several discrete point masses, the center of mass lies at...
02:57Coordination Number and Geometry
For transition metal complexes, the coordination number determines the geometry around the central metal ion. Table 1 compares coordination numbers to molecular geometry. The most common structures of the complexes in coordination compounds are octahedral, tetrahedral, and square planar.