Fast Marching
   HOME





Fast Marching
The fast marching methodJ.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591--1595, 1996/ref> is a numerical method created by James Sethian for solving boundary value problems of the Eikonal equation: : , \nabla u(x), =1/f(x) \text x \in \Omega : u(x) = 0 \text x \in \partial \Omega Typically, such a problem describes the evolution of a closed surface as a function of time u with speed f in the normal direction at a point x on the propagating surface. The speed function is specified, and the time at which the contour crosses a point x is obtained by solving the equation. Alternatively, u(x) can be thought of as the minimum amount of time it would take to reach \partial\Omega starting from the point x. The fast marching method takes advantage of this optimal control interpretation of the problem in order to build a solution outwards starting from the "known information", i.e. the boundary values. The algorithm ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Numerical Method
In numerical analysis, a numerical method is a mathematical tool designed to solve numerical problems. The implementation of a numerical method with an appropriate convergence check in a programming language is called a numerical algorithm. Mathematical definition Let F(x,y)=0 be a well-posed problem, i.e. F:X \times Y \rightarrow \mathbb is a real or complex functional relationship, defined on the Cartesian product of an input data set X and an output data set Y, such that exists a locally lipschitz function g:X \rightarrow Y called resolvent, which has the property that for every root (x,y) of F, y=g(x). We define numerical method for the approximation of F(x,y)=0, the sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ... of problems : \left \_ = \left \_, with F_n:X_n ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


James Sethian
James Albert Sethian is a professor of mathematics at the University of California, Berkeley and the head of the Mathematics Grouat the United States Department of Energy, United States Department of Energy's Lawrence Berkeley National Laboratory. Sethian was born in Washington, D.C., on May 10, 1954. He received a B.A. (1976) from Princeton and a M.A. (1978) and Ph.D (1982) from Berkeley under the direction of Alexandre Chorin. Beginning in 1983, he was a National Science Foundation postdoctoral fellow, lastly at the Courant Institute under Peter Lax. In 1985, he returned to Berkeley to join the mathematics faculty, where he is currently a full professor. Sethian was elected member of the National Academy of Engineering in 2008 as well as the National Academy of Sciences in 2013. Sethian has acted as Interim Director Research at Thinking Machines Corporation and held visiting positions at the National Center for Atmospheric Research and the National Institute of Standards a ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Boundary Value Problem
In the study of differential equations, a boundary-value problem is a differential equation subjected to constraints called boundary conditions. A solution to a boundary value problem is a solution to the differential equation which also satisfies the boundary conditions. Boundary value problems arise in several branches of physics as any physical differential equation will have them. Problems involving the wave equation, such as the determination of normal modes, are often stated as boundary value problems. A large class of important boundary value problems are the Sturm–Liouville problems. The analysis of these problems, in the linear case, involves the eigenfunctions of a differential operator. To be useful in applications, a boundary value problem should be well posed. This means that given the input to the problem there exists a unique solution, which depends continuously on the input. Much theoretical work in the field of partial differential equations is devot ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Eikonal Equation
An eikonal equation (from Greek εἰκών, image) is a non-linear first-order partial differential equation that is encountered in problems of wave propagation. The classical eikonal equation in geometric optics is a differential equation of the form where x lies in an open subset of \mathbb^n, n(x) is a positive function, \nabla denotes the gradient, and , \cdot , is the Euclidean norm. The function n is given and one seeks solutions u . In the context of geometric optics, the function n is the refractive index of the medium. More generally, an eikonal equation is an equation of the form where H is a function of 2n variables. Here the function H is given, and u is the solution. If H(x,y)= , y, - n(x) , then equation () becomes (). Eikonal equations naturally arise in the WKB method and the study of Maxwell's equations. Eikonal equations provide a link between physical (wave) optics and geometric (ray) optics. One fast computational algorithm t ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Optimal Control
Optimal control theory is a branch of control theory that deals with finding a control for a dynamical system over a period of time such that an objective function is optimized. It has numerous applications in science, engineering and operations research. For example, the dynamical system might be a spacecraft with controls corresponding to rocket thrusters, and the objective might be to reach the Moon with minimum fuel expenditure. Or the dynamical system could be a nation's economy, with the objective to minimize unemployment; the controls in this case could be fiscal and monetary policy. A dynamical system may also be introduced to embed operations research problems within the framework of optimal control theory. Optimal control is an extension of the calculus of variations, and is a mathematical optimization method for deriving control policies. The method is largely due to the work of Lev Pontryagin and Richard Bellman in the 1950s, after contributions to calculus of v ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Dijkstra's Algorithm
Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. Dijkstra's algorithm finds the shortest path from a given source node to every other node. It can be used to find the shortest path to a specific destination node, by terminating the algorithm after determining the shortest path to the destination node. For example, if the nodes of the graph represent cities, and the costs of edges represent the distances between pairs of cities connected by a direct road, then Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. A common application of shortest path algorithms is network routing protocols, most notably IS-IS (Intermediate System to Intermediate System) and OSPF (Open Shortest Path First). It is also employed as a subroutine in ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Ron Kimmel
Ron Kimmel (; born 1963) is a professor of Computer Science and Electrical and Computer Engineering (by courtesy) at the Technion Israel Institute of Technology. He holds a D.Sc. degree in electrical engineering (1995) from the Technion and was a post-doc at UC Berkeley and Berkeley Labs, and a visiting professor at Stanford University. He has worked in various areas of image and shape analysis in computer vision, image processing, and computer graphics. Kimmel's interest in recent years has been non-rigid shape processing and analysis, medical imaging, computational biometry, deep learning, numerical optimization of problems with a geometric flavor, and applications of metric and differential geometry. Kimmel is an author of two books, an editor of one, and an author of numerous articles. He is the founder of the Geometric Image Processing La and a founder and advisor of several successful image processing and analysis companies. Kimmel's contributions include the development of ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Partial Differential Equation
In mathematics, a partial differential equation (PDE) is an equation which involves a multivariable function and one or more of its partial derivatives. The function is often thought of as an "unknown" that solves the equation, similar to how is thought of as an unknown number solving, e.g., an algebraic equation like . However, it is usually impossible to write down explicit formulae for solutions of partial differential equations. There is correspondingly a vast amount of modern mathematical and scientific research on methods to numerically approximate solutions of certain partial differential equations using computers. Partial differential equations also occupy a large sector of pure mathematical research, in which the usual questions are, broadly speaking, on the identification of general qualitative features of solutions of various partial differential equations, such as existence, uniqueness, regularity and stability. Among the many open questions are the existence ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Fast Sweeping Method
In applied mathematics, the fast sweeping method is a numerical method for solving boundary value problems of the Eikonal equation. : , \nabla u(\mathbf), = \frac 1 \text \mathbf \in \Omega : u(\mathbf) = 0 \text \mathbf \in \partial \Omega where \Omega is an open set in \mathbb^n, f(\mathbf) is a function with positive values, \partial \Omega is a well-behaved boundary of the open set and , \cdot, is the Euclidean norm. The fast sweeping method is an iterative method which uses upwind difference for discretization and uses Gauss–Seidel iterations with alternating sweeping ordering to solve the discretized Eikonal equation on a rectangular grid. The origins of this approach lie in the paper by Boue and Dupuis. Although fast sweeping methods have existed in control theory, it was first proposed for Eikonal equations by Hongkai Zhao, an applied mathematician at the University of California, Irvine The University of California, Irvine (UCI or UC Irvine) is a Public ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Bellman–Ford Algorithm
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex (graph theory), vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.Lecture 14
stanford.edu
The algorithm was first proposed by , but is instead named after Richard Bellman and L. R. Ford Jr., Lester Ford Jr., who published it in #, 1958 and #, 1956, respectively. Edward F. Moore also published a variation of the algorithm in #, 1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm. Negative edge weights are found in various applications of graph ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]