Related Experiment Video
Updated: May 29, 2026
13:28
High-resolution Single Particle Analysis from Electron Cryo-microscopy Images Using SPHIRE
Published on: May 16, 2017
A refinement of a spherical decomposition algorithm
1Department of Computer and Information Science, Moore School of Electrical Engineering, University of Pennsylvania, Philadelphia, PA 19104; CRIN, C.O. 140, 54047 Nancy Cedex, Franc.
IEEE Transactions on Pattern Analysis and Machine Intelligence
|August 27, 2011
Summary
This study refines the O'Rourke-Badler spherical decomposition algorithm, significantly improving computational efficiency. The enhanced algorithm reduces complexity from cubic (O(n3)) to quadratic (O(n2)).
Area of Science:
- Computational geometry
- Computer-aided design (CAD)
Background:
- Spherical decomposition is crucial for complex geometric modeling.
- Existing algorithms like O'Rourke-Badler have high computational complexity.
Purpose of the Study:
- To propose a refined spherical decomposition algorithm.
- To reduce the algorithmic complexity of spherical decomposition.
Main Methods:
- Modification of the O'Rourke-Badler spherical decomposition algorithm.
- Analysis of algorithmic complexity.
Main Results:
- The refined algorithm achieves a complexity of O(n2).
- This represents a significant reduction from the original O(n3) complexity.
Conclusions:
- The proposed refinement offers a more efficient approach to spherical decomposition.
- This advancement has implications for improving performance in CAD and geometric modeling applications.
Related Concept Videos
01:23Spherical Coordinates
Spherical coordinate systems are preferred over Cartesian, polar, or cylindrical coordinates for systems with spherical symmetry. For example, to describe the surface of a sphere, Cartesian coordinates require all three coordinates. On the other hand, the spherical coordinate system requires only one parameter: the sphere's radius. As a result, the complicated mathematical calculations become simple. Spherical coordinates are used in science and engineering applications like electric and...
01:12Theorems of Pappus and Guldinus: Problem Solving
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a cylinder...
01:29Volumes of Solids of Revolution
Volumes of irregularly shaped objects can be systematically determined using the concept of solids of revolution. This approach begins with a region defined by a curve in a two-dimensional plane. When this region is rotated about a fixed line, known as the axis of revolution, it generates a three-dimensional object with rotational symmetry. Such objects frequently arise in mathematical modeling, physics, and engineering applications.When the region being rotated lies directly against the axis...
01:26Gauss's Law: Spherical Symmetry
A charge distribution has spherical symmetry if the density of charge depends only on the distance from a point in space and not on the direction. In other words, if the system is rotated, it doesn't look different. For instance, if a sphere of radius R is uniformly charged with charge density ρ0, then the distribution has spherical symmetry. On the other hand, if a sphere of radius R is charged so that the top half of the sphere has a uniform charge density ρ1 and the bottom half has a uniform...
01:28Partial Fractions
A partial fraction is a component of a rational expression represented as the sum of simpler fractions. When a rational function is expressed as a ratio of two polynomials, it can often be decomposed into a sum of fractions whose denominators are simpler polynomials, typically linear or irreducible quadratic factors. This process is called partial fraction decomposition, and it is used to simplify complex expressions for integration, solving equations, or analysis.Partial fraction decomposition...
01:23Trigonometric Substitution
Trigonometric substitution is a technique used to simplify integrals that contain square root expressions involving quadratic forms. It is particularly effective when the integrand includes terms resembling those found in standard geometric equations, such as circles or ellipses.Molniya satellites follow highly elliptical orbits, repeatedly sweeping out the same regions of space as they revolve around Earth. To estimate the area enclosed by such an orbit, the path is modeled as an ellipse...