Discrete Morse theory is a
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many app ...
adaptation of
Morse theory
In mathematics, specifically in differential topology, Morse theory enables one to analyze the topology of a manifold by studying differentiable functions on that manifold. According to the basic insights of Marston Morse, a typical differentiabl ...
developed by
Robin Forman
Robin may refer to:
Animals
* Australasian robins, red-breasted songbirds of the family Petroicidae
* Many members of the subfamily Saxicolinae (Old World chats), including:
**European robin (''Erithacus rubecula'')
** Bush-robin
**Forest r ...
. The theory has various practical applications in diverse fields of
applied mathematics
Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathematical s ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, such as
configuration spaces,
homology
Homology may refer to:
Sciences
Biology
*Homology (biology), any characteristic of biological organisms that is derived from a common ancestor
* Sequence homology, biological homology between DNA, RNA, or protein sequences
*Homologous chrom ...
computation,
denoising
Noise reduction is the process of removing noise from a signal. Noise reduction techniques exist for audio and images. Noise reduction algorithms may distort the signal to some degree. Noise rejection is the ability of a circuit to isolate an un ...
,
mesh compression, and
topological data analysis
In applied mathematics, topological based data analysis (TDA) is an approach to the analysis of datasets using techniques from topology. Extraction of information from datasets that are high-dimensional, incomplete and noisy is generally challengin ...
.
Notation regarding CW complexes
Let
be a
CW complex
A CW complex (also called cellular complex or cell complex) is a kind of a topological space that is particularly important in algebraic topology. It was introduced by J. H. C. Whitehead (open access) to meet the needs of homotopy theory. This cla ...
and denote by
its set of cells. Define the ''incidence function''
in the following way: given two cells
and
in
, let
be the
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
of the
attaching map In mathematics, an adjunction space (or attaching space) is a common construction in topology where one topological space is attached or "glued" onto another. Specifically, let ''X'' and ''Y'' be topological spaces, and let ''A'' be a subspace of ' ...
from the boundary of
to
. The
boundary operator
In mathematics, a chain complex is an algebraic structure that consists of a sequence of abelian groups (or modules) and a sequence of homomorphisms between consecutive groups such that the image of each homomorphism is included in the kernel of t ...
is the endomorphism
of the free abelian group generated by
defined by
:
It is a defining property of boundary operators that
. In more axiomatic definitions one can find the requirement that
:
which is a consequence of the above definition of the boundary operator and the requirement that
.
Discrete Morse functions
A
real
Real may refer to:
Currencies
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Music Albums
* ''Real'' (L'Arc-en-Ciel album) (2000)
* ''Real'' (Bright album) (2010)
...
-valued function
is a ''discrete Morse function'' if it satisfies the following two properties:
# For any cell
, the number of cells
in the boundary of
which satisfy
is at most one.
# For any cell
, the number of cells
containing
in their boundary which satisfy
is at most one.
It can be shown that the cardinalities in the two conditions cannot both be one simultaneously for a fixed cell
, provided that
is a ''regular'' CW complex. In this case, each cell
can be paired with at most one exceptional cell
: either a boundary cell with larger
value, or a co-boundary cell with smaller
value. The cells which have no pairs, i.e., whose function values are strictly higher than their boundary cells and strictly lower than their co-boundary cells are called ''critical'' cells. Thus, a discrete Morse function partitions the CW complex into three distinct cell collections:
, where:
#
denotes the critical cells which are unpaired,
#
denotes cells which are paired with boundary cells, and
#
denotes cells which are paired with co-boundary cells.
By construction, there is a
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
of
sets between
-dimensional cells in
and the
-dimensional cells in
, which can be denoted by
for each
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
. It is an additional technical requirement that for each
, the degree of the attaching map from the boundary of
to its paired cell
is a
unit
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (alb ...
in the underlying
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
of
. For instance, over the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s
, the only allowed values are
. This technical requirement is guaranteed, for instance, when one assumes that
is a regular CW complex over
.
The fundamental result of discrete Morse theory establishes that the CW complex
is
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
on the level of
homology
Homology may refer to:
Sciences
Biology
*Homology (biology), any characteristic of biological organisms that is derived from a common ancestor
* Sequence homology, biological homology between DNA, RNA, or protein sequences
*Homologous chrom ...
to a new complex
consisting of only the critical cells. The paired cells in
and
describe ''gradient paths'' between adjacent critical cells which can be used to obtain the boundary operator on
. Some details of this construction are provided in the next section.
The Morse complex
A ''gradient path'' is a sequence of paired cells
:
satisfying
and
. The ''index'' of this gradient path is defined to be the integer
:
The division here makes sense because the incidence between paired cells must be
. Note that by construction, the values of the discrete Morse function
must decrease across
. The path
is said to ''connect'' two critical cells
if
. This relationship may be expressed as
. The ''multiplicity'' of this connection is defined to be the integer
. Finally, the Morse boundary operator on the critical cells
is defined by
:
where the sum is taken over all gradient path connections from
to
.
Basic Results
Many of the familiar results from continuous Morse theory apply in the discrete setting.
The Morse Inequalities
Let
be a Morse complex associated to the CW complex
. The number
of
-cells in
is called the
-th ''Morse number''. Let
denote the
-th
Betti number
In algebraic topology, the Betti numbers are used to distinguish topological spaces based on the connectivity of ''n''-dimensional simplicial complexes. For the most reasonable finite-dimensional spaces (such as compact manifolds, finite simplicia ...
of
. Then, for any
, the following inequalities hold
:
, and
:
Moreover, the
Euler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space ...
of
satisfies
:
Discrete Morse Homology and Homotopy Type
Let
be a regular CW complex with boundary operator
and a discrete Morse function
. Let
be the associated Morse complex with Morse boundary operator
. Then, there is an
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
of
homology
Homology may refer to:
Sciences
Biology
*Homology (biology), any characteristic of biological organisms that is derived from a common ancestor
* Sequence homology, biological homology between DNA, RNA, or protein sequences
*Homologous chrom ...
groups
:
and similarly for the homotopy groups.
Applications
Discrete Morse theory finds its application in molecular shape analysis, skeletonization of digital images/volumes, graph reconstruction from noisy data, denoising noisy point clouds
and analysing
lithic tools in
archaeology
Archaeology or archeology is the scientific study of human activity through the recovery and analysis of material culture. The archaeological record consists of artifacts, architecture, biofacts or ecofacts, sites, and cultural landscap ...
.
See also
*
Digital Morse theory In mathematics, digital Morse theory is a digital adaptation of continuum Morse theory for scalar volume data. This is not about the Samuel Morse's Morse code of long and short clicks or tones used in manual electric telegraphy. The term was fir ...
*
Stratified Morse theory In mathematics, stratified Morse theory is an analogue to Morse theory for general stratified spaces, originally developed by Mark Goresky and Robert MacPherson. The main point of the theory is to consider functions f : M \to \mathbb R and consid ...
*
Shape analysis
*
Topological combinatorics The mathematical discipline of topological combinatorics is the application of topological and algebro-topological methods to solving problems in combinatorics.
History
The discipline of combinatorial topology used combinatorial concepts in topo ...
*
Discrete differential geometry
Discrete differential geometry is the study of discrete counterparts of notions in differential geometry. Instead of smooth curves and surfaces, there are polygons, meshes, and simplicial complexes. It is used in the study of computer graphics, ge ...
References
*
*
*
*
*
*
{{refend
Combinatorics
Morse theory
Computational topology