<< Chapter < Page Chapter >> Page >

Alpha-shapes

Part of the problem with defining the shape of a protein is that we start with nothing but a point set, and the "shape" of a set of discontinuous points is poorly defined. The problem is, what do we mean by shape? As you saw above, the shape of a molecule depends on what is being used to measure it. To handle this ambiguity, we will introduce a method of shape calculation based on a parameter, α, which will determine the radius of a spherical probe that will define the surface. The method defines a class of shapes, called α-shapes for any given point set. It allows fast, accurate, and efficient calculations of volume and surface area.

α-shapes are a generalization of the convex hull . Consider a point set S. Define an α-ball as a sphere of radius α. An α-ball is empty if it contains no points in S. For any α between zero and infinity, the α-hull of S is the complement of the union of all empty α-balls.

  • For α of infinity, the α-shape is the convex hull of S.
  • For α smaller than the 1/2 smallest distance between two points in S, the α-shape is S itself.
  • For any α in between, one can think of the α-hull as the largest polygon (polyhedron) or set thereof whose vertices are in the point set and whose edges are of length less than 2α. The presence of an edge indicates that a probe of radius α cannot pass between the edge endpoints.

Two-dimensional α-shapes

Some α-shapes are shown for a point set and various values of α. On the left, α is 0 or slightly more, such that an α-ball can fit between any two points in the set. The α-shape is therefore the original point set. On the right, α is infinity, so an α-ball can be approximated locally by a line. α on this scale yields the convex hull of the point set. The middle image shows the α-shape for α equal to the radius of the ball shown. This yields two disjoint boundaries, one of which has a significant indentation. Voids , or empty pockets completely enclosed by the α-shape, are also possible, for instance if the α-shape is ring-like (in 2D) or forms a hollow shell (in 3D).

Computing the alpha-shape: delaunay triangulation

A triangulation of a three-dimensional point set S is any decomposition of S into non-intersecting tetrahedra (triangles for two-dimensional point sets). The Delaunay triangulation of S is the unique triangulation of S satisfying the additional requirement that no sphere circumscribing a tetrahedron in the triangulation contains any point in S. Although it is incidental to α-shapes, it is worth noting that the Delaunay triangulation maximizes the average of the smallest angle over all triangles. In other words, it favors relatively even-sided triangles over sharp and stretched ones.

Two-dimensional delaunay triangulation

The Delaunay triangulation of the four points given is shown on the right. Note that the circumscribing circles on the left each contain one point of S, whereas the circles on the right do not. The transition from the triangulation on the left to that on the right is called an edge flip, and is the basic operation of constructing a two-dimensional Delaunay triangulation. Face flipping is the analogous procedure for five points in three dimensions.
The Delaunay triangulation of a point set is usually calculated by an incremental flip algorithm as follows:
  • The points of S are sorted on one coordinate (x, y, or z). This step is not strictly necessary but makes the algorithm run faster than if the points were in arbitrary order.
  • Each point is added in sorted order. Upon adding a point:
    • The point is connected to previously added points that are "visible" to it, that is, to points to which it can be connected by a line segment without passing through a face of a tetrahedron.
    • Any new tetrhedra formed are checked and flipped if necessary.
    • Any tetrahedra adjacent to flipped tetrahedra are checked and flipped. This continues until further flipping is unnecessary, which is guaranteed to occur
This algorithm runs in worst case O(n^2) time, but expected O(n^(3/2)) time. Without the sort in the first step, the expected case would be O(n log n) . A full description and analysis of Delaunay triangulation algorithms is given in [1] , chapter 9.

Questions & Answers

the diagram of the digestive system
Assiatu Reply
How does twins formed
William Reply
They formed in two ways first when one sperm and one egg are splited by mitosis or two sperm and two eggs join together
Oluwatobi
what is genetics
Josephine Reply
Genetics is the study of heredity
Misack
how does twins formed?
Misack
What is manual
Hassan Reply
discuss biological phenomenon and provide pieces of evidence to show that it was responsible for the formation of eukaryotic organelles
Joseph Reply
what is biology
Yousuf Reply
the study of living organisms and their interactions with one another and their environments
AI-Robot
the study of living organisms and their interactions with one another and their environment.
Wine
discuss the biological phenomenon and provide pieces of evidence to show that it was responsible for the formation of eukaryotic organelles in an essay form
Joseph Reply
what is the blood cells
Shaker Reply
list any five characteristics of the blood cells
Shaker
lack electricity and its more savely than electronic microscope because its naturally by using of light
Abdullahi Reply
advantage of electronic microscope is easily and clearly while disadvantage is dangerous because its electronic. advantage of light microscope is savely and naturally by sun while disadvantage is not easily,means its not sharp and not clear
Abdullahi
cell theory state that every organisms composed of one or more cell,cell is the basic unit of life
Abdullahi
is like gone fail us
DENG
cells is the basic structure and functions of all living things
Ramadan
What is classification
ISCONT Reply
is organisms that are similar into groups called tara
Yamosa
in what situation (s) would be the use of a scanning electron microscope be ideal and why?
Kenna Reply
A scanning electron microscope (SEM) is ideal for situations requiring high-resolution imaging of surfaces. It is commonly used in materials science, biology, and geology to examine the topography and composition of samples at a nanoscale level. SEM is particularly useful for studying fine details,
Hilary
cell is the building block of life.
Condoleezza Reply
what is cell divisoin?
Aron Reply
Diversity of living thing
ISCONT
what is cell division
Aron Reply
Cell division is the process by which a single cell divides into two or more daughter cells. It is a fundamental process in all living organisms and is essential for growth, development, and reproduction. Cell division can occur through either mitosis or meiosis.
AI-Robot
What is life?
Allison Reply
life is defined as any system capable of performing functions such as eating, metabolizing,excreting,breathing,moving,Growing,reproducing,and responding to external stimuli.
Mohamed
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Geometric methods in structural computational biology. OpenStax CNX. Jun 11, 2007 Download for free at http://cnx.org/content/col10344/1.6
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Geometric methods in structural computational biology' conversation and receive update notifications?

Ask