User:Ab3080888/数学沙盒

A pictorial representation of a simple linear program with two variables and six inequalities. The set of feasible solutions is depicted in yellow and forms a polygon, a 2-dimensional polytope. The optimum of the linear cost function is where the red line intersects the polygon. The red line is a level set of the cost function, and the arrow indicates the direction in which we are optimizing.

A closed feasible region of a problem with three variables is a convex polyhedron. The surfaces giving a fixed value of the objective function are planes (not shown). The linear programming problem is to find a point on the polyhedron that is on the plane with the highest possible value.

线性规划（英語：Linear Programming，简称LP）是一种数学方法，通过线性方程或不等式描述问题的约束条件和目标，以实现最佳结果（例如利润最大化或成本最小化）。作为最优化的一种特例，线性规划在许多领域都有重要应用。

更严谨地说，线性规划旨在优化一个线性目标函数，该函数需满足一定的线性等式和不等式约束。其解的可行域是一个凸多面体，这一区域由若干线性不等式描述的有限半空间的交集定义。目标函数本质上是定义在这一凸多面体上的实值仿射函数。通过线性规划算法，可以在多面体内找到目标函数的最大值或最小值（若解存在）。

线性规划问题通常用标准形式表达为：

${\begin{aligned}&{\text{Find a vector}}&&\mathbf {x} \\&{\text{that maximizes}}&&\mathbf {c} ^{\mathsf {T}}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}$

其中，$\mathbf {x}$是待求解的变量向量，$\mathbf {c}$和$\mathbf {b}$是已知向量，$A$是已知矩阵。需要最大化的$\mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x}$被称为目标函数，而约束条件$A\mathbf {x} \leq \mathbf {b}$和$\mathbf {x} \geq \mathbf {0}$定义了目标函数优化范围内的凸多面体。

线性规划的应用覆盖多个领域。它在数学研究中尤为常见，同时也在商业、经济学以及某些工程问题中具有重要价值。线性规划与特征方程、冯·诺依曼的总体均衡模型及结构均衡模型紧密相关（详见對偶線性規劃）。 目前，运输、能源、电信和制造业等行业广泛使用线性规划模型。通过这种方法，可以高效解决规划、路由、日程安排、任务分配和设计等各类复杂问题，为实际应用提供精确的数学支持。

History

Leonid Kantorovich

John von Neumann

The problem of solving a system of linear inequalities dates back at least as far as Fourier, who in 1827 published a method for solving them, and after whom the method of Fourier–Motzkin elimination is named.

In the late 1930s, Soviet mathematician Leonid Kantorovich and American economist Wassily Leontief independently delved into the practical applications of linear programming. Kantorovich focused on manufacturing schedules, while Leontief explored economic applications. Their groundbreaking work was largely overlooked for decades.

The turning point came during World War II when linear programming emerged as a vital tool. It found extensive use in addressing complex wartime challenges, including transportation logistics, scheduling, and resource allocation. Linear programming proved invaluable in optimizing these processes while considering critical constraints such as costs and resource availability.

Despite its initial obscurity, the wartime successes propelled linear programming into the spotlight. Post-WWII, the method gained widespread recognition and became a cornerstone in various fields, from operations research to economics. The overlooked contributions of Kantorovich and Leontief in the late 1930s eventually became foundational to the broader acceptance and utilization of linear programming in optimizing decision-making processes.

Kantorovich's work was initially neglected in the USSR. About the same time as Kantorovich, the Dutch-American economist T. C. Koopmans formulated classical economic problems as linear programs. Kantorovich and Koopmans later shared the 1975 Nobel Memorial Prize in Economic Sciences. In 1941, Frank Lauren Hitchcock also formulated transportation problems as linear programs and gave a solution very similar to the later simplex method. Hitchcock had died in 1957, and the Nobel Memorial Prize is not awarded posthumously.

From 1946 to 1947 George B. Dantzig independently developed general linear programming formulation to use for planning problems in the US Air Force. In 1947, Dantzig also invented the simplex method that, for the first time efficiently, tackled the linear programming problem in most cases. When Dantzig arranged a meeting with John von Neumann to discuss his simplex method, von Neumann immediately conjectured the theory of duality by realizing that the problem he had been working in game theory was equivalent. Dantzig provided formal proof in an unpublished report "A Theorem on Linear Inequalities" on January 5, 1948. Dantzig's work was made available to public in 1951. In the post-war years, many industries applied it in their daily planning.

Dantzig's original example was to find the best assignment of 70 people to 70 jobs. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the observable universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the simplex algorithm. The theory behind linear programming drastically reduces the number of possible solutions that must be checked.

The linear programming problem was first shown to be solvable in polynomial time by Leonid Khachiyan in 1979, but a larger theoretical and practical breakthrough in the field came in 1984 when Narendra Karmarkar introduced a new interior-point method for solving linear-programming problems.

Uses

Linear programming is a widely used field of optimization for several reasons. Many practical problems in operations research can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems, are considered important enough to have much research on specialized algorithms. A number of algorithms for other types of optimization problems work by solving linear programming problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. Likewise, linear programming was heavily used in the early formation of microeconomics, and it is currently utilized in company management, such as planning, production, transportation, and technology. Although the modern management issues are ever-changing, most companies would like to maximize profits and minimize costs with limited resources. Google also uses linear programming to stabilize YouTube videos.

Standard form

Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following three parts:

• A linear (or affine) function to be maximized

e.g. $f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}$

• Problem constraints of the following form

e.g.

${\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}$

• Non-negative variables

e.g.

${\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}$

The problem is usually expressed in matrix form, and then becomes:

$\max\{\,\mathbf {c} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}$

Other forms, such as minimization problems, problems with constraints on alternative forms, and problems involving negative variables can always be rewritten into an equivalent problem in standard form.

Example

Graphical solution to the farmer example – after shading regions violating the conditions, the vertex of the unshaded region with the dashed line farthest from the origin gives the optimal combination (its lying on the land and pesticide lines implies that revenue is limited by land and pesticide, not fertilizer)

Suppose that a farmer has a piece of farm land, say L hectares, to be planted with either wheat or barley or some combination of the two. The farmer has F kilograms of fertilizer and P kilograms of pesticide. Every hectare of wheat requires F₁ kilograms of fertilizer and P₁ kilograms of pesticide, while every hectare of barley requires F₂ kilograms of fertilizer and P₂ kilograms of pesticide. Let S₁ be the selling price of wheat and S₂ be the selling price of barley, per hectare. If we denote the area of land planted with wheat and barley by x₁ and x₂ respectively, then profit can be maximized by choosing optimal values for x₁ and x₂. This problem can be expressed with the following linear programming problem in the standard form:

Maximize:	$S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$	(maximize the revenue (the total wheat sales plus the total barley sales) – revenue is the "objective function")
Subject to:	$x_{1}+x_{2}\leq L$	(limit on total area)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F$	(limit on fertilizer)
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P$	(limit on pesticide)
	$x_{1}\geq 0,x_{2}\geq 0$	(cannot plant a negative area).

In matrix form this becomes:

maximize ${\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}$

subject to ${\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.$

Augmented form (slack form)

Linear programming problems can be converted into an augmented form in order to apply the common form of the simplex algorithm. This form introduces non-negative slack variables to replace inequalities with equalities in the constraints. The problems can then be written in the following block matrix form:

Maximize $z$:

${\begin{bmatrix}1&-\mathbf {c} ^{\mathsf {T}}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}$

$\mathbf {x} \geq 0,\mathbf {s} \geq 0$

where $\mathbf {s}$ are the newly introduced slack variables, $\mathbf {x}$ are the decision variables, and $z$ is the variable to be maximized.

Example

The example above is converted into the following augmented form:

Maximize: $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		(objective function)
subject to:	$x_{1}+x_{2}+x_{3}=L$	(augmented constraint)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F$	(augmented constraint)
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P$	(augmented constraint)
	$x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.$

where $x_{3},x_{4},x_{5}$ are (non-negative) slack variables, representing in this example the unused area, the amount of unused fertilizer, and the amount of unused pesticide.

In matrix form this becomes:

Maximize $z$:

$${\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.$$

Duality

主条目：Dual linear program

Every linear programming problem, referred to as a primal problem, can be converted into a dual problem, which provides an upper bound to the optimal value of the primal problem. In matrix form, we can express the primal problem as:

Maximize c^Tx subject to Ax ≤ b, x ≥ 0;

with the corresponding symmetric dual problem,

Minimize b^Ty subject to A^Ty ≥ c, y ≥ 0.

An alternative primal formulation is:

Maximize c^Tx subject to Ax ≤ b;

with the corresponding asymmetric dual problem,

Minimize b^Ty subject to A^Ty = c, y ≥ 0.

There are two ideas fundamental to duality theory. One is the fact that (for the symmetric dual) the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual. The weak duality theorem states that the objective function value of the dual at any feasible solution is always greater than or equal to the objective function value of the primal at any feasible solution. The strong duality theorem states that if the primal has an optimal solution, x^*, then the dual also has an optimal solution, y^*, and c^Tx^*=b^Ty^*.

A linear program can also be unbounded or infeasible. Duality theory tells us that if the primal is unbounded then the dual is infeasible by the weak duality theorem. Likewise, if the dual is unbounded, then the primal must be infeasible. However, it is possible for both the dual and the primal to be infeasible. See dual linear program for details and several more examples.

Variations

Covering/packing dualities

A covering LP is a linear program of the form:

Minimize: b^Ty,

subject to: A^Ty ≥ c, y ≥ 0,

such that the matrix A and the vectors b and c are non-negative.

The dual of a covering LP is a packing LP, a linear program of the form:

Maximize: c^Tx,

subject to: Ax ≤ b, x ≥ 0,

such that the matrix A and the vectors b and c are non-negative.

Examples

Covering and packing LPs commonly arise as a linear programming relaxation of a combinatorial problem and are important in the study of approximation algorithms. For example, the LP relaxations of the set packing problem, the independent set problem, and the matching problem are packing LPs. The LP relaxations of the set cover problem, the vertex cover problem, and the dominating set problem are also covering LPs.

Finding a fractional coloring of a graph is another example of a covering LP. In this case, there is one constraint for each vertex of the graph and one variable for each independent set of the graph.

Complementary slackness

It is possible to obtain an optimal solution to the dual when only an optimal solution to the primal is known using the complementary slackness theorem. The theorem states:

Suppose that x = (x₁, x₂, ... , x_n) is primal feasible and that y = (y₁, y₂, ... , y_m) is dual feasible. Let (w₁, w₂, ..., w_m) denote the corresponding primal slack variables, and let (z₁, z₂, ... , z_n) denote the corresponding dual slack variables. Then x and y are optimal for their respective problems if and only if

• x_j z_j = 0, for j = 1, 2, ... , n, and
• w_i y_i = 0, for i = 1, 2, ... , m.

So if the i-th slack variable of the primal is not zero, then the i-th variable of the dual is equal to zero. Likewise, if the j-th slack variable of the dual is not zero, then the j-th variable of the primal is equal to zero.

This necessary condition for optimality conveys a fairly simple economic principle. In standard form (when maximizing), if there is slack in a constrained primal resource (i.e., there are "leftovers"), then additional quantities of that resource must have no value. Likewise, if there is slack in the dual (shadow) price non-negativity constraint requirement, i.e., the price is not zero, then there must be scarce supplies (no "leftovers").

Theory

Existence of optimal solutions

Geometrically, the linear constraints define the feasible region, which is a convex polytope. A linear function is a convex function, which implies that every local minimum is a global minimum; similarly, a linear function is a concave function, which implies that every local maximum is a global maximum.

An optimal solution need not exist, for two reasons. First, if the constraints are inconsistent, then no feasible solution exists: For instance, the constraints x ≥ 2 and x ≤ 1 cannot be satisfied jointly; in this case, we say that the LP is infeasible. Second, when the polytope is unbounded in the direction of the gradient of the objective function (where the gradient of the objective function is the vector of the coefficients of the objective function), then no optimal value is attained because it is always possible to do better than any finite value of the objective function.

Optimal vertices (and rays) of polyhedra

Otherwise, if a feasible solution exists and if the constraint set is bounded, then the optimum value is always attained on the boundary of the constraint set, by the maximum principle for convex functions (alternatively, by the minimum principle for concave functions) since linear functions are both convex and concave. However, some problems have distinct optimal solutions; for example, the problem of finding a feasible solution to a system of linear inequalities is a linear programming problem in which the objective function is the zero function (i.e., the constant function taking the value zero everywhere). For this feasibility problem with the zero-function for its objective-function, if there are two distinct solutions, then every convex combination of the solutions is a solution.

The vertices of the polytope are also called basic feasible solutions. The reason for this choice of name is as follows. Let d denote the number of variables. Then the fundamental theorem of linear inequalities implies (for feasible problems) that for every vertex x^* of the LP feasible region, there exists a set of d (or fewer) inequality constraints from the LP such that, when we treat those d constraints as equalities, the unique solution is x^*. Thereby we can study these vertices by means of looking at certain subsets of the set of all constraints (a discrete set), rather than the continuum of LP solutions. This principle underlies the simplex algorithm for solving linear programs.

Algorithms

参见：List of numerical analysis topics § Linear programming

In a linear programming problem, a series of linear constraints produces a convex feasible region of possible values for those variables. In the two-variable case this region is in the shape of a convex simple polygon.

Basis exchange algorithms

Simplex algorithm of Dantzig

The simplex algorithm, developed by George Dantzig in 1947, solves LP problems by constructing a feasible solution at a vertex of the polytope and then walking along a path on the edges of the polytope to vertices with non-decreasing values of the objective function until an optimum is reached for sure. In many practical problems, "stalling" occurs: many pivots are made with no increase in the objective function. In rare practical problems, the usual versions of the simplex algorithm may actually "cycle". To avoid cycles, researchers developed new pivoting rules.

In practice, the simplex algorithm is quite efficient and can be guaranteed to find the global optimum if certain precautions against cycling are taken. The simplex algorithm has been proved to solve "random" problems efficiently, i.e. in a cubic number of steps, which is similar to its behavior on practical problems.

However, the simplex algorithm has poor worst-case behavior: Klee and Minty constructed a family of linear programming problems for which the simplex method takes a number of steps exponential in the problem size. In fact, for some time it was not known whether the linear programming problem was solvable in polynomial time, i.e. of complexity class P.

Criss-cross algorithm

Like the simplex algorithm of Dantzig, the criss-cross algorithm is a basis-exchange algorithm that pivots between bases. However, the criss-cross algorithm need not maintain feasibility, but can pivot rather from a feasible basis to an infeasible basis. The criss-cross algorithm does not have polynomial time-complexity for linear programming. Both algorithms visit all 2^D corners of a (perturbed) cube in dimension D, the Klee–Minty cube, in the worst case.

Interior point

In contrast to the simplex algorithm, which finds an optimal solution by traversing the edges between vertices on a polyhedral set, interior-point methods move through the interior of the feasible region.

Ellipsoid algorithm, following Khachiyan

This is the first worst-case polynomial-time algorithm ever found for linear programming. To solve a problem which has n variables and can be encoded in L input bits, this algorithm runs in $O(n^{6}L)$ time. Leonid Khachiyan solved this long-standing complexity issue in 1979 with the introduction of the ellipsoid method. The convergence analysis has (real-number) predecessors, notably the iterative methods developed by Naum Z. Shor and the approximation algorithms by Arkadi Nemirovski and D. Yudin.

Projective algorithm of Karmarkar

主条目：Karmarkar's algorithm

Khachiyan's algorithm was of landmark importance for establishing the polynomial-time solvability of linear programs. The algorithm was not a computational break-through, as the simplex method is more efficient for all but specially constructed families of linear programs.

However, Khachiyan's algorithm inspired new lines of research in linear programming. In 1984, N. Karmarkar proposed a projective method for linear programming. Karmarkar's algorithm improved on Khachiyan's worst-case polynomial bound (giving $O(n^{3.5}L)$). Karmarkar claimed that his algorithm was much faster in practical LP than the simplex method, a claim that created great interest in interior-point methods. Since Karmarkar's discovery, many interior-point methods have been proposed and analyzed.

Vaidya's 87 algorithm

In 1987, Vaidya proposed an algorithm that runs in $O(n^{3})$ time.

Vaidya's 89 algorithm

In 1989, Vaidya developed an algorithm that runs in $O(n^{2.5})$ time. Formally speaking, the algorithm takes $O((n+d)^{1.5}nL)$ arithmetic operations in the worst case, where $d$ is the number of constraints, $n$ is the number of variables, and $L$ is the number of bits.

Input sparsity time algorithms

In 2015, Lee and Sidford showed that linear programming can be solved in ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ time, where ${\tilde {O}}$ denotes the soft O notation, and $nnz(A)$ represents the number of non-zero elements, and it remains taking $O(n^{2.5}L)$ in the worst case.

Current matrix multiplication time algorithm

In 2019, Cohen, Lee and Song improved the running time to ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ time, $\omega$ is the exponent of matrix multiplication and $\alpha$ is the dual exponent of matrix multiplication. $\alpha$ is (roughly) defined to be the largest number such that one can multiply an $n\times n$ matrix by a $n\times n^{\alpha }$ matrix in $O(n^{2})$ time. In a followup work by Lee, Song and Zhang, they reproduce the same result via a different method. These two algorithms remain ${\tilde {O}}(n^{2+1/6}L)$ when $\omega =2$ and $\alpha =1$. The result due to Jiang, Song, Weinstein and Zhang improved ${\tilde {O}}(n^{2+1/6}L)$ to ${\tilde {O}}(n^{2+1/18}L)$.

Comparison of interior-point methods and simplex algorithms

The current opinion is that the efficiencies of good implementations of simplex-based methods and interior point methods are similar for routine applications of linear programming. However, for specific types of LP problems, it may be that one type of solver is better than another (sometimes much better), and that the structure of the solutions generated by interior point methods versus simplex-based methods are significantly different with the support set of active variables being typically smaller for the latter one.

Open problems and recent work

There are several open problems in the theory of linear programming, the solution of which would represent fundamental breakthroughs in mathematics and potentially major advances in our ability to solve large-scale linear programs.

• Does LP admit a strongly polynomial-time algorithm?
• Does LP admit a strongly polynomial-time algorithm to find a strictly complementary solution?
• Does LP admit a polynomial-time algorithm in the real number (unit cost) model of computation?

This closely related set of problems has been cited by Stephen Smale as among the 18 greatest unsolved problems of the 21st century. In Smale's words, the third version of the problem "is the main unsolved problem of linear programming theory." While algorithms exist to solve linear programming in weakly polynomial time, such as the ellipsoid methods and interior-point techniques, no algorithms have yet been found that allow strongly polynomial-time performance in the number of constraints and the number of variables. The development of such algorithms would be of great theoretical interest, and perhaps allow practical gains in solving large LPs as well.

Although the Hirsch conjecture was recently disproved for higher dimensions, it still leaves the following questions open.

• Are there pivot rules which lead to polynomial-time simplex variants?
• Do all polytopal graphs have polynomially bounded diameter?

These questions relate to the performance analysis and development of simplex-like methods. The immense efficiency of the simplex algorithm in practice despite its exponential-time theoretical performance hints that there may be variations of simplex that run in polynomial or even strongly polynomial time. It would be of great practical and theoretical significance to know whether any such variants exist, particularly as an approach to deciding if LP can be solved in strongly polynomial time.

The simplex algorithm and its variants fall in the family of edge-following algorithms, so named because they solve linear programming problems by moving from vertex to vertex along edges of a polytope. This means that their theoretical performance is limited by the maximum number of edges between any two vertices on the LP polytope. As a result, we are interested in knowing the maximum graph-theoretical diameter of polytopal graphs. It has been proved that all polytopes have subexponential diameter. The recent disproof of the Hirsch conjecture is the first step to prove whether any polytope has superpolynomial diameter. If any such polytopes exist, then no edge-following variant can run in polynomial time. Questions about polytope diameter are of independent mathematical interest.

Simplex pivot methods preserve primal (or dual) feasibility. On the other hand, criss-cross pivot methods do not preserve (primal or dual) feasibility – they may visit primal feasible, dual feasible or primal-and-dual infeasible bases in any order. Pivot methods of this type have been studied since the 1970s. Essentially, these methods attempt to find the shortest pivot path on the arrangement polytope under the linear programming problem. In contrast to polytopal graphs, graphs of arrangement polytopes are known to have small diameter, allowing the possibility of strongly polynomial-time criss-cross pivot algorithm without resolving questions about the diameter of general polytopes.

Integer unknowns

If all of the unknown variables are required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) NP-hard. 0–1 integer programming or binary integer programming (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version was one of Karp's 21 NP-complete problems.

If only some of the unknown variables are required to be integers, then the problem is called a mixed integer (linear) programming (MIP or MILP) problem. These are generally also NP-hard because they are even more general than ILP programs.

There are however some important subclasses of IP and MIP problems that are efficiently solvable, most notably problems where the constraint matrix is totally unimodular and the right-hand sides of the constraints are integers or – more general – where the system has the total dual integrality (TDI) property.

Advanced algorithms for solving integer linear programs include:

• cutting-plane method
• Branch and bound
• Branch and cut
• Branch and price
• if the problem has some extra structure, it may be possible to apply delayed column generation.

Such integer-programming algorithms are discussed by Padberg and in Beasley.

Integral linear programs

更多信息：Integral polytope

A linear program in real variables is said to be integral if it has at least one optimal solution which is integral, i.e., made of only integer values. Likewise, a polyhedron $P=\{x\mid Ax\geq 0\}$ is said to be integral if for all bounded feasible objective functions c, the linear program $\{\max cx\mid x\in P\}$ has an optimum $x^{*}$ with integer coordinates. As observed by Edmonds and Giles in 1977, one can equivalently say that the polyhedron $P$ is integral if for every bounded feasible integral objective function c, the optimal value of the linear program $\{\max cx\mid x\in P\}$ is an integer.

Integral linear programs are of central importance in the polyhedral aspect of combinatorial optimization since they provide an alternate characterization of a problem. Specifically, for any problem, the convex hull of the solutions is an integral polyhedron; if this polyhedron has a nice/compact description, then we can efficiently find the optimal feasible solution under any linear objective. Conversely, if we can prove that a linear programming relaxation is integral, then it is the desired description of the convex hull of feasible (integral) solutions.

Terminology is not consistent throughout the literature, so one should be careful to distinguish the following two concepts,

• in an integer linear program, described in the previous section, variables are forcibly constrained to be integers, and this problem is NP-hard in general,
• in an integral linear program, described in this section, variables are not constrained to be integers but rather one has proven somehow that the continuous problem always has an integral optimal value (assuming c is integral), and this optimal value may be found efficiently since all polynomial-size linear programs can be solved in polynomial time.

One common way of proving that a polyhedron is integral is to show that it is totally unimodular. There are other general methods including the integer decomposition property and total dual integrality. Other specific well-known integral LPs include the matching polytope, lattice polyhedra, submodular flow polyhedra, and the intersection of two generalized polymatroids/g-polymatroids – e.g. see Schrijver 2003.

Solvers and scripting (programming) languages

Permissive licenses:

Name	License	Brief info
Gekko	MIT License	Open-source library for solving large-scale LP, QP, QCQP, NLP, and MIP optimization
GLOP	Apache v2	Google's open-source linear programming solver
JuMP	MPL License	Open-source modeling language with solvers for large-scale LP, QP, QCQP, SDP, SOCP, NLP, and MIP optimization
Pyomo	BSD	An open-source modeling language for large-scale linear, mixed integer and nonlinear optimization
SCIP	Apache v2	A general-purpose constraint integer programming solver with an emphasis on MIP. Compatible with Zimpl modelling language.
SuanShu	Apache v2	An open-source suite of optimization algorithms to solve LP, QP, SOCP, SDP, SQP in Java

Copyleft (reciprocal) licenses:

Name	License	Brief info
ALGLIB	GPL 2+	An LP solver from ALGLIB project (C++, C#, Python)
Cassowary constraint solver	LGPL	An incremental constraint solving toolkit that efficiently solves systems of linear equalities and inequalities
CLP	CPL	An LP solver from COIN-OR
glpk	GPL	GNU Linear Programming Kit, an LP/MILP solver with a native C API and numerous (15) third-party wrappers for other languages. Specialist support for flow networks. Bundles the AMPL-like GNU MathProg modelling language and translator.
lp solve	LGPL v2.1	An LP and MIP solver featuring support for the MPS format and its own "lp" format, as well as custom formats through its "eXternal Language Interface" (XLI). Translating between model formats is also possible.
Qoca	GPL	A library for incrementally solving systems of linear equations with various goal functions
R-Project	GPL	A programming language and software environment for statistical computing and graphics

MINTO (Mixed Integer Optimizer, an integer programming solver which uses branch and bound algorithm) has publicly available source code but is not open source.

Proprietary licenses:

Name	Brief info
AIMMS	A modeling language that allows to model linear, mixed integer, and nonlinear optimization models. It also offers a tool for constraint programming. Algorithm, in the forms of heuristics or exact methods, such as Branch-and-Cut or Column Generation, can also be implemented. The tool calls an appropriate solver such as CPLEX or similar, to solve the optimization problem at hand. Academic licenses are free of charge.
ALGLIB	A commercial edition of the copyleft licensed library. C++, C#, Python.
AMPL	A popular modeling language for large-scale linear, mixed integer and nonlinear optimisation with a free student limited version available (500 variables and 500 constraints).
Analytica	A general modeling language and interactive development environment. Its influence diagrams enable users to formulate problems as graphs with nodes for decision variables, objectives, and constraints. Analytica Optimizer Edition includes linear, mixed integer, and nonlinear solvers and selects the solver to match the problem. It also accepts other engines as plug-ins, including XPRESS, Gurobi, Artelys Knitro, and MOSEK.
APMonitor	API to MATLAB and Python. Solve example Linear Programming (LP) problems through MATLAB, Python, or a web-interface.
CPLEX	Popular solver with an API for several programming languages, and also has a modelling language and works with AIMMS, AMPL, GAMS, MPL, OpenOpt, OPL Development Studio, and TOMLAB. Free for academic use.
Excel Solver Function	A nonlinear solver adjusted to spreadsheets in which function evaluations are based on the recalculating cells. Basic version available as a standard add-on for Excel.
FortMP
GAMS
Gurobi Optimizer
IMSL Numerical Libraries	Collections of math and statistical algorithms available in C/C++, Fortran, Java and C#/.NET. Optimization routines in the IMSL Libraries include unconstrained, linearly and nonlinearly constrained minimizations, and linear programming algorithms.
LINDO	Solver with an API for large scale optimization of linear, integer, quadratic, conic and general nonlinear programs with stochastic programming extensions. It offers a global optimization procedure for finding guaranteed globally optimal solution to general nonlinear programs with continuous and discrete variables. It also has a statistical sampling API to integrate Monte-Carlo simulations into an optimization framework. It has an algebraic modeling language (LINGO) and allows modeling within a spreadsheet (What'sBest).
Maple	A general-purpose programming-language for symbolic and numerical computing.
MATLAB	A general-purpose and matrix-oriented programming-language for numerical computing. Linear programming in MATLAB requires the Optimization Toolbox in addition to the base MATLAB product; available routines include INTLINPROG and LINPROG
Mathcad	A WYSIWYG math editor. It has functions for solving both linear and nonlinear optimization problems.
Mathematica	A general-purpose programming-language for mathematics, including symbolic and numerical capabilities.
MOSEK	A solver for large scale optimization with API for several languages (C++, java, .net, Matlab and python).
NAG Numerical Library	A collection of mathematical and statistical routines developed by the Numerical Algorithms Group for multiple programming languages (C, C++, Fortran, Visual Basic, Java and C#) and packages (MATLAB, Excel, R, LabVIEW). The Optimization chapter of the NAG Library includes routines for linear programming problems with both sparse and non-sparse linear constraint matrices, together with routines for the optimization of quadratic, nonlinear, sums of squares of linear or nonlinear functions with nonlinear, bounded or no constraints. The NAG Library has routines for both local and global optimization, and for continuous or integer problems.
OptimJ	A Java-based modeling language for optimization with a free version available.
SAS/OR	A suite of solvers for Linear, Integer, Nonlinear, Derivative-Free, Network, Combinatorial and Constraint Optimization; the Algebraic modeling language OPTMODEL; and a variety of vertical solutions aimed at specific problems/markets, all of which are fully integrated with the SAS System.
XPRESS	Solver for large-scale linear programs, quadratic programs, general nonlinear and mixed-integer programs. Has API for several programming languages, also has a modelling language Mosel and works with AMPL, GAMS. Free for academic use.
VisSim	A visual block diagram language for simulation of dynamical systems.

See also

• Convex programming
• Dynamic programming
• Expected shortfall § Optimization of expected shortfall
• Input–output model
• Job shop scheduling
• Least absolute deviations
• Least-squares spectral analysis
• Linear algebra
• Linear production game
• Linear-fractional programming (LFP)
• LP-type problem
• Mathematical programming
• Nonlinear programming
• Odds algorithm used to solve optimal stopping problems
• Oriented matroid
• Quadratic programming, a superset of linear programming
• Semidefinite programming
• Shadow price
• Simplex algorithm, used to solve LP problems

References

• Kantorovich, L. V. Об одном эффективном методе решения некоторых классов экстремальных проблем [A new method of solving some classes of extremal problems]. Doklady Akad Sci SSSR. 1940, 28: 211–214. 
• F. L. Hitchcock: The distribution of a product from several sources to numerous localities, Journal of Mathematics and Physics, 20, 1941, 224–230.
• G.B Dantzig: Maximization of a linear function of variables subject to linear inequalities, 1947. Published pp. 339–347 in T.C. Koopmans (ed.):Activity Analysis of Production and Allocation, New York-London 1951 (Wiley & Chapman-Hall)
• J. E. Beasley, editor. Advances in Linear and Integer Programming. Oxford Science, 1996. (Collection of surveys)
• Bland, Robert G. New Finite Pivoting Rules for the Simplex Method. Mathematics of Operations Research. 1977, 2 (2): 103–107. JSTOR 3689647. doi:10.1287/moor.2.2.103. 
• Borgwardt, Karl-Heinz. The Simplex Algorithm: A Probabilistic Analysis. Algorithms and Combinatorics 1. Springer-Verlag. 1987.  (Average behavior on random problems)
• Richard W. Cottle, ed. The Basic George B. Dantzig. Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Selected papers by George B. Dantzig)
• George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
• Dantzig, George B.; Thapa, Mukund N. Linear Programming 2: Theory and Extensions. Springer-Verlag. 2003.  (Comprehensive, covering e.g. pivoting and interior-point algorithms, large-scale problems, decomposition following Dantzig–Wolfe and Benders, and introducing stochastic programming.)
• Edmonds, Jack; Giles, Rick. A Min-Max Relation for Submodular Functions on Graphs. Studies in Integer Programming. Annals of Discrete Mathematics 1. 1977: 185–204. ISBN 978-0-7204-0765-5. doi:10.1016/S0167-5060(08)70734-9. 
• Fukuda, Komei; Terlaky, Tamás. Thomas M. Liebling; Dominique de Werra , 编. Criss-cross methods: A fresh view on pivot algorithms. Mathematical Programming, Series B. 1997, 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373 . MR 1464775. S2CID 2794181. doi:10.1007/BF02614325. 
• Gondzio, Jacek; Terlaky, Tamás. 3 A computational view of interior point methods. J. E. Beasley (编). Advances in linear and integer programming. Oxford Lecture Series in Mathematics and its Applications 4. New York: Oxford University Press. 1996: 103–144. MR 1438311. Postscript file at website of Gondzio and at McMaster University website of Terlaky. 
• Murty, Katta G. Linear programming. New York: John Wiley & Sons, Inc. 1983: xix+482. ISBN 978-0-471-09725-9. MR 0720547. (comprehensive reference to classical approaches). 
• Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)
• Padberg, M. Linear Optimization and Extensions, Second Edition. Springer-Verlag. 1999.  (carefully written account of primal and dual simplex algorithms and projective algorithms, with an introduction to integer linear programming – featuring the traveling salesman problem for Odysseus.)
• Papadimitriou, Christos H.; Steiglitz, Kenneth. Combinatorial Optimization: Algorithms and Complexity Corrected republication with a new preface. Dover.  (computer science)
• Todd, Michael J. The many facets of linear programming. Mathematical Programming. February 2002, 91 (3): 417–436. S2CID 6464735. doi:10.1007/s101070100261.  (Invited survey, from the International Symposium on Mathematical Programming.)
• Vanderbei, Robert J. Linear Programming: Foundations and Extensions. Springer Verlag. 2001. 
• Vazirani, Vijay V. Approximation Algorithms. Springer-Verlag. 2001. ISBN 978-3-540-65367-7.  (Computer science)

Further reading

• Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Solutions, Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)
• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried. Computational Geometry 2nd revised. Springer-Verlag. 2000. ISBN 978-3-540-65620-3.  含有內容需登入查看的頁面 (link) Chapter 4: Linear Programming: pp. 63–94. Describes a randomized half-plane intersection algorithm for linear programming.
• Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. 1979. ISBN 978-0-7167-1045-5.  A6: MP1: INTEGER PROGRAMMING, pg.245. (computer science, complexity theory)
• Template:Cite Gartner Matousek 2006 (elementary introduction for mathematicians and computer scientists)
• Cornelis Roos, Tamás Terlaky, Jean-Philippe Vial, Interior Point Methods for Linear Optimization, Second Edition, Springer-Verlag, 2006. (Graduate level)
• Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency. Springer. 2003. 
• Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6 (mathematical)
• Gerard Sierksma; Yori Zwols. Linear and Integer Optimization: Theory and Practice. CRC Press. 2015. ISBN 978-1-498-71016-9. 
• Gerard Sierksma; Diptesh Ghosh. Networks in Action; Text and Computer Exercises in Network Optimization. Springer. 2010. ISBN 978-1-4419-5512-8.  (linear optimization modeling)
• H. P. Williams, Model Building in Mathematical Programming, Fifth Edition, 2013. (Modeling)
• Stephen J. Wright, 1997, Primal-Dual Interior-Point Methods, SIAM. (Graduate level)
• Yinyu Ye, 1997, Interior Point Algorithms: Theory and Analysis, Wiley. (Advanced graduate-level)
• Ziegler, Günter M., Chapters 1–3 and 6–7 in Lectures on Polytopes, Springer-Verlag, New York, 1994. (Geometry)

External links

• Guidance On Formulating LP Problems
• Mathematical Programming Glossary
• The Linear Programming FAQ
• Benchmarks For Optimisation Software

A geodesic on an oblate ellipsoid

The study of geodesics on an ellipsoid arose in connection with geodesy specifically with the solution of triangulation networks. The figure of the Earth is well approximated by an oblate ellipsoid, a slightly flattened sphere. A geodesic is the shortest path between two points on a curved surface, i.e., the analogue of a straight line on a plane surface. The solution of a triangulation network on an ellipsoid is therefore a set of exercises in spheroidal trigonometry (Euler 1755).

Isaac Newton

Leonhard Euler

If the Earth is treated as a sphere, the geodesics are great circles (all of which are closed) and the problems reduce to ones in spherical trigonometry. However, Newton (1687) showed that the effect of the rotation of the Earth results in its resembling a slightly oblate ellipsoid and, in this case, the equator and the meridians are the only closed geodesics. Furthermore, the shortest path between two points on the equator does not necessarily run along the equator. Finally, if the ellipsoid is further perturbed to become a triaxial ellipsoid (with three distinct semi-axes), then only three geodesics are closed and one of these is unstable.

The problems in geodesy are usually reduced to two main cases: the direct problem, given a starting point and an initial heading, find the position after traveling a certain distance along the geodesic; and the inverse problem, given two points on the ellipsoid find the connecting geodesic and hence the shortest distance between them. Because the flattening of the Earth is small, the geodesic distance between two points on the Earth is well approximated by the great-circle distance using the mean Earth radius—the relative error is less than 1%. However, the course of the geodesic can differ dramatically from that of the great circle. As an extreme example, consider two points on the equator with a longitude difference of 179°59′; while the connecting great circle follows the equator, the shortest geodesics pass within 180 km of either pole (the flattening makes two symmetric paths passing close to the poles shorter than the route along the equator).

Aside from their use in geodesy and related fields such as navigation, terrestrial geodesics arise in the study of the propagation of signals which are confined (approximately) to the surface of the Earth, for example, sound waves in the ocean (Munk & Forbes 1989) and the radio signals from lightning (Casper & Bent 1991). Geodesics are used to define some maritime boundaries, which in turn determine the allocation of valuable resources as such oil and mineral rights. Ellipsoidal geodesics also arise in other applications; for example, the propagation of radio waves along the fuselage of an aircraft, which can be roughly modeled as a prolate (elongated) ellipsoid (Kim & Burnside 1986).

Geodesics are an important intrinsic characteristic of curved surfaces. The sequence of progressively more complex surfaces, the sphere, an ellipsoid of revolution, and a triaxial ellipsoid, provide a useful family of surfaces for investigating the general theory of surfaces. Indeed, Gauss's work on the survey of Hanover, which involved geodesics on an oblate ellipsoid, was a key motivation for his study of surfaces (Gauss 1828). Similarly, the existence of three closed geodesics on a triaxial ellipsoid turns out to be a general property of closed, simply connected surfaces; this was conjectured by Poincaré (1905) and proved by Lyusternik & Schnirelmann (1929) (Klingenberg 1982，§3.7).

Geodesics on an ellipsoid of revolution

There are several ways of defining geodesics (Hilbert & Cohn-Vossen 1952，第220–221頁). A simple definition is as the shortest path between two points on a surface. However, it is frequently more useful to define them as paths with zero geodesic curvature—i.e., the analogue of straight lines on a curved surface. This definition encompasses geodesics traveling so far across the ellipsoid's surface (somewhat less than half the circumference) that other distinct routes require less distance. Locally, these geodesics are still identical to the shortest distance between two points.

By the end of the 18th century, an ellipsoid of revolution (the term spheroid is also used) was a well-accepted approximation to the figure of the Earth. The adjustment of triangulation networks entailed reducing all the measurements to a reference ellipsoid and solving the resulting two-dimensional problem as an exercise in spheroidal trigonometry (Bomford 1952，Chap. 3).

Fig. 1. A geodesic AB on an ellipsoid of revolution. N is the north pole and EFH lie on the equator.

It is possible to reduce the various geodesic problems into one of two types. Consider two points: A at latitude φ₁ and longitude λ₁ and B at latitude φ₂ and longitude λ₂ (see Fig. 1). The connecting geodesic (from A to B) is AB, of length s₁₂, which has azimuths α₁ and α₂ at the two endpoints. The two geodesic problems usually considered are:

1. the direct geodesic problem or first geodesic problem, given A, α₁, and s₁₂, determine B and α₂;
2. the inverse geodesic problem or second geodesic problem, given A and B, determine s₁₂, α₁, and α₂.

As can be seen from Fig. 1, these problems involve solving the triangle NAB given one angle, α₁ for the direct problem and λ₁₂ = λ₂ − λ₁ for the inverse problem, and its two adjacent sides. In the course of the 18th century these problems were elevated (especially in literature in the German language) to the principal geodesic problems (Hansen 1865，第69頁).

For a sphere the solutions to these problems are simple exercises in spherical trigonometry, whose solution is given by formulas for solving a spherical triangle. (See the article on great-circle navigation.)

Alexis Clairaut

Barnaba Oriani

For an ellipsoid of revolution, the characteristic constant defining the geodesic was found by Clairaut (1735). A systematic solution for the paths of geodesics was given by Legendre (1806) and Oriani (1806) (and subsequent papers in 1808 and 1810). The full solution for the direct problem (complete with computational tables and a worked out example) is given by Bessel (1825).

Much of the early work on these problems was carried out by mathematicians—for example, Legendre, Bessel, and Gauss—who were also heavily involved in the practical aspects of surveying. Beginning in about 1830, the disciplines diverged: those with an interest in geodesy concentrated on the practical aspects such as approximations suitable for field work, while mathematicians pursued the solution of geodesics on a triaxial ellipsoid, the analysis of the stability of closed geodesics, etc.

During the 18th century geodesics were typically referred to as "shortest lines". The term "geodesic line" was coined by Laplace (1799b):

Nous désignerons cette ligne sous le nom de ligne géodésique [We will call this line the geodesic line].

This terminology was introduced into English either as "geodesic line" or as "geodetic line", for example (Hutton 1811),

A line traced in the manner we have now been describing, or deduced from trigonometrical measures, by the means we have indicated, is called a geodetic or geodesic line: it has the property of being the shortest which can be drawn between its two extremities on the surface of the Earth; and it is therefore the proper itinerary measure of the distance between those two points.

In its adoption by other fields "geodesic line", frequently shortened, to "geodesic", was preferred.

This section treats the problem on an ellipsoid of revolution (both oblate and prolate). The problem on a triaxial ellipsoid is covered in the next section.

When determining distances on the earth, various approximate methods are frequently used; some of these are described in the article on geographical distance.

Equations for a geodesic

Friedrich Bessel

Fig. 2. Differential element of a meridian ellipse.

Fig. 3. Differential element of a geodesic on an ellipsoid.

Here the equations for a geodesic are developed; these allow the geodesics of any length to be computed accurately. The following derivation closely follows that of Bessel (1825). Bagratuni (1962，§15), Krakiwsky & Thomson (1974，§4), Rapp (1993，§1.2), and Borre & Strang (2012) also provide derivations of these equations.

Consider an ellipsoid of revolution with equatorial radius a and polar semi-axis b. Define the flattening f = (a − b)/a, the eccentricity e² = f(2 − f), and the second eccentricity e′ = e/(1 − f). (In most applications in geodesy, the ellipsoid is taken to be oblate, a > b; however, the theory applies without change to prolate ellipsoids, a < b, in which case f, e², and e′² are negative.)

Let an elementary segment of a path on the ellipsoid have length ds. From Figs. 2 and 3, we see that if its azimuth is α, then ds is related to dφ and dλ by

(1)${\color {white}.}\qquad \cos \alpha \,ds=\rho \,d\phi =-dR/\sin \phi ,\quad \sin \alpha \,ds=R\,d\lambda ,$

where ρ is the meridional radius of curvature, R = ν cosφ is the radius of the circle of latitude φ, and ν is the normal radius of curvature. The elementary segment is therefore given by

$ds^{2}=\rho ^{2}\,d\phi ^{2}+R^{2}\,d\lambda ^{2}$

or

${\begin{aligned}ds&={\sqrt {\rho ^{2}\phi '^{2}+R^{2}}}\,d\lambda \\&\equiv L(\phi ,\phi ')\,d\lambda ,\end{aligned}}$

where φ′ = dφ/dλ and L depends on φ through ρ(φ) and R(φ). The length of an arbitrary path between (φ₁, λ₁) and (φ₂, λ₂) is given by

$s_{12}=\int _{\lambda _{1}}^{\lambda _{2}}L(\phi ,\phi ')\,d\lambda ,$

where φ is a function of λ satisfying φ(λ₁) = φ₁ and φ(λ₂) = φ₂. The shortest path or geodesic entails finding that function φ(λ) which minimizes s₁₂. This is an exercise in the calculus of variations and the minimizing condition is given by the Beltrami identity,

$L-\phi '{\frac {\partial L}{\partial \phi '}}={\text{const.}}$

Fig. 4. The geometric construction for parametric latitude, β. A point P at latitude φ on the meridian (red) is mapped to a point P′ on a sphere of radius a (shown as a blue circle) by keeping the radius R constant.

Substituting for L and using Eqs. (1) gives

$R\sin \alpha ={\text{const.}}$

Clairaut (1735) first found this relation, using a geometrical construction; a similar derivation is presented by Lyusternik (1964，§10). Differentiating this relation and manipulating the result gives (Jekeli 2012，Eq. (2.95))

$d\alpha =\sin \phi \,d\lambda .$

This, together with Eqs. (1), leads to a system of ordinary differential equations for a geodesic (Borre & Strang 2012，Eqs. (11.71) and (11.76))

(2)${\color {white}.}\qquad \displaystyle {\frac {d\phi }{ds}}={\frac {\cos \alpha }{\rho }};\quad {\frac {d\lambda }{ds}}={\frac {\sin \alpha }{\nu \cos \phi }};\quad {\frac {d\alpha }{ds}}={\frac {\tan \phi \sin \alpha }{\nu }}.$

We can express R in terms of the parametric latitude, β, using

$R=a\cos \beta$

(see Fig. 4 for the geometrical construction), and Clairaut's relation then becomes

$\sin \alpha _{1}\cos \beta _{1}=\sin \alpha _{2}\cos \beta _{2}.$

Fig. 5. Geodesic problem mapped to the auxiliary sphere.

Fig. 6. The elementary geodesic problem on the auxiliary sphere.

This is the sine rule of spherical trigonometry relating two sides of the triangle NAB (see Fig. 5), NA = ½π − β₁, and NB = ½π − β₂ and their opposite angles B = π − α₂ and A = α₁.

In order to find the relation for the third side AB = σ₁₂, the spherical arc length, and included angle N = ω₁₂, the spherical longitude, it is useful to consider the triangle NEP representing a geodesic starting at the equator; see Fig. 6. In this figure, the variables referred to the auxiliary sphere are shown with the corresponding quantities for the ellipsoid shown in parentheses. Quantities without subscripts refer to the arbitrary point P; E, the point at which the geodesic crosses the equator in the northward direction, is used as the origin for σ, s and ω.

Fig. 7. Differential element of a geodesic on a sphere.

If the side EP is extended by moving P infinitesimally (see Fig. 7), we obtain

(3)${\color {white}.}\qquad \cos \alpha \,d\sigma =d\beta ,\quad \sin \alpha \,d\sigma =\cos \beta \,d\omega .$

Combining Eqs. (1) and (3) gives differential equations for s and λ

${\frac {1}{a}}{\frac {ds}{d\sigma }}={\frac {d\lambda }{d\omega }}={\frac {\sin \beta }{\sin \phi }}.$

Up to this point, we have not made use of the specific equations for an ellipsoid, and indeed the derivation applies to an arbitrary surface of revolution. Bessel now specializes to an ellipsoid in which R and Z are related by

${\frac {R^{2}}{a^{2}}}+{\frac {Z^{2}}{b^{2}}}=1,$

where Z is the height above the equator (see Fig. 4). Differentiating this and setting dR/dZ = −sinφ/cosφ gives

${\frac {R\sin \phi }{a^{2}}}-{\frac {Z\cos \phi }{b^{2}}}=0;$

eliminating Z from these equations, we obtain

${\frac {R}{a}}=\cos \beta ={\frac {\cos \phi }{\sqrt {1-e^{2}\sin ^{2}\phi }}}.$

This relation between β and φ can be written as

$\tan \beta ={\sqrt {1-e^{2}}}\tan \phi =(1-f)\tan \phi ,$

which is the normal definition of the parametric latitude on an ellipsoid. Furthermore, we have

${\frac {\sin \beta }{\sin \phi }}={\sqrt {1-e^{2}\cos ^{2}\beta }},$

so that the differential equations for the geodesic become

${\frac {1}{a}}{\frac {ds}{d\sigma }}={\frac {d\lambda }{d\omega }}={\sqrt {1-e^{2}\cos ^{2}\beta }}.$

The last step is to use σ as the independent parameter in both of these differential equations and thereby to express s and λ as integrals. Applying the sine rule to the vertices E and G in the spherical triangle EGP in Fig. 6 gives

$\sin \beta =\sin \beta (\sigma ;\alpha _{0})=\cos \alpha _{0}\sin \sigma ,$

where α₀ is the azimuth at E. Substituting this into the equation for ds/dσ and integrating the result gives

(4)${\color {white}.}\qquad {\begin{aligned}{\frac {s}{b}}&=\int _{0}^{\sigma }{\frac {\sqrt {1-e^{2}\cos ^{2}\beta (\sigma ';\alpha _{0})}}{1-f}}\,d\sigma '\\&=\int _{0}^{\sigma }{\sqrt {1+k^{2}\sin ^{2}\sigma '}}\,d\sigma ',\end{aligned}}$

where

$k=e'\cos \alpha _{0},$

and the limits on the integral are chosen so that s(σ = 0) = 0. Legendre (1811，第180頁) pointed out that the equation for s is the same as the equation for the arc on an ellipse with semi-axes b(1 + e′² cos²α₀)^1/2 and b. In order to express the equation for λ in terms of σ, we write

$d\omega ={\frac {\sin \alpha _{0}}{\cos ^{2}\beta }}\,d\sigma ,$

which follows from Eq. (3) and Clairaut's relation. This yields

(5)${\color {white}.}\qquad {\begin{aligned}\lambda -\lambda _{0}&=(1-f)\sin \alpha _{0}\int _{0}^{\sigma }{\frac {\sqrt {1+k^{2}\sin ^{2}\sigma '}}{1-\cos ^{2}\alpha _{0}\sin ^{2}\sigma '}}\,d\sigma '\\&=\omega -\sin \alpha _{0}\int _{0}^{\sigma }{\frac {e^{2}}{1+{\sqrt {1-e^{2}\cos ^{2}\beta (\sigma ';\alpha _{0})}}}}\,d\sigma '\\&=\omega -f\sin \alpha _{0}\int _{0}^{\sigma }{\frac {2-f}{1+(1-f){\sqrt {1+k^{2}\sin ^{2}\sigma '}}}}\,d\sigma ',\end{aligned}}$

and the limits on the integrals are chosen so that λ = λ₀ at the equator crossing, σ = 0.

In using these integral relations, we allow σ to increase continuously (not restricting it to a range [−π, π], for example) as the great circle, resp. geodesic, encircles the auxiliary sphere, resp. ellipsoid. The quantities ω, λ, and s are likewise allowed to increase without limit. Once the problem is solved, λ can be reduced to the conventional range.

This completes the solution of the path of a geodesic using the auxiliary sphere. By this device a great circle can be mapped exactly to a geodesic on an ellipsoid of revolution. However, because the equations for s and λ in terms of the spherical quantities depend on α₀, the mapping is not a consistent mapping of the surface of the sphere to the ellipsoid or vice versa; instead, it should be viewed merely as a convenient tool for solving for a particular geodesic.

There are also several ways of approximating geodesics on an ellipsoid which usually apply for sufficiently short lines (Rapp 1991，§6); however, these are typically comparable in complexity to the method for the exact solution given above (Jekeli 2012，§2.1.4).

Behavior of geodesics

Fig. 8. Meridians and the equator are the only closed geodesics. (For the very flattened ellipsoids, there are other closed geodesics; see Figs. 13 and 14).

Geodesic on an oblate ellipsoid (f = 1/50) with α₀ = 45°.

Fig. 9. Latitude as a function of longitude for a single cycle of the geodesic from one northward equatorial crossing to the next.

Fig. 10. Following the geodesic on the ellipsoid for about 5 circuits.

Fig. 11. The same geodesic after about 70 circuits.

Fig. 12. Geodesic on a prolate ellipsoid (f = −1/50) with α₀ = 45°. Compare with Fig. 10.

Before solving for the geodesics, it is worth reviewing their behavior. Fig. 8 shows the simple closed geodesics which consist of the meridians (green) and the equator (red). (Here the qualification "simple" means that the geodesic closes on itself without an intervening self-intersection.) This follows from the equations for the geodesics given in the previous section.

For meridians, we have α₀ = 0 and Eq. (5) becomes λ = ω + λ₀, i.e., the longitude will vary the same way as for a sphere, jumping by π each time the geodesic crosses the pole. The distance, Eq. (4), reduces to the length of an arc of an ellipse with semi-axes a and b (as expected), expressed in terms of parametric latitude, β.

The equator (β = 0 on the auxiliary sphere, φ = 0 on the ellipsoid) corresponds to α₀ = ½π. The distance reduces to the arc of a circle of radius b (and not a), s = bσ, while the longitude simplifies to λ = (1 − f)σ + λ₀. A geodesic that is nearly equatorial will intersect the equator at intervals of πb. As a consequence, the maximum length of a equatorial geodesic which is also a shortest path is πb on an oblate ellipsoid (on a prolate ellipsoid, the maximum length is πa).

All other geodesics are typified by Figs. 9 to 11. Figure 9 shows latitude as a function of longitude for a geodesic starting on the equator with α₀ = 45°. A full cycle of the geodesic, from one northward crossing of the equator to the next, is shown. The equatorial crossings are called nodes and the points of maximum or minimum latitude are called vertices; the vertex latitudes are given by |β| = ±(½π − |α₀|). The latitude is an odd, resp. even, function of the longitude about the nodes, resp. vertices. The geodesic completes one full oscillation in latitude before the longitude has increased by 360°. Thus, on each successive northward crossing of the equator (see Fig. 10), λ falls short of a full circuit of the equator by approximately 2π f sinα₀ (for a prolate ellipsoid, this quantity is negative and λ completes more that a full circuit; see Fig. 12). For nearly all values of α₀, the geodesic will fill that portion of the ellipsoid between the two vertex latitudes (see Fig. 11).

Two additional closed geodesics for the oblate ellipsoid, b/a = 2/7.

Fig. 13. Side view.

Fig. 14. Top view.

If the ellipsoid is sufficiently oblate, i.e., b/a < ½, another class of simple closed geodesics is possible (Klingenberg 1982，§3.5.19). Two such geodesics are illustrated in Figs. 13 and 14. Here b/a = 2/7 and the equatorial azimuth, α₀, for the green (resp. blue) geodesic is chosen to be 53.175° (resp. 75.192°), so that the geodesic completes 2 (resp. 3) complete oscillations about the equator on one circuit of the ellipsoid.

Evaluation of the integrals

Solving the geodesic problems entails evaluating the integrals for the distance, s, and the longitude, λ, Eqs. (4) and (5). In geodetic applications, where f is small, the integrals are typically evaluated as a series; for this purpose, the second form of the longitude integral is preferred (since it avoids the near singular behavior of the first form when geodesics pass close to a pole). In both integrals, the integrand is an even periodic function of period π. Furthermore, the term dependent on σ is multiplied by a small quantity k² = O(f). As a consequence, the integrals can both be written in the form

$I=B_{0}\sigma +\sum _{j=1}^{\infty }B_{j}\sin 2j\sigma$

where B₀ = 1 + O(f) and B_j = O(f ^j). Series expansions for B_j can readily be found and the result truncated so that only terms which are O(f ^J) and larger are retained. (Because the longitude integral is multiplied by f, it is typically only necessary to retain terms up to O(f ^J−1) in that integral.) This prescription is followed by many authors (Legendre 1806) (Oriani 1806) (Bessel 1825) (Helmert 1880) (Rainsford 1955) (Rapp 1993). Vincenty (1975a) uses J = 3 which provides an accuracy of about 0.1 mm for the WGS84 ellipsoid. Karney (2013) gives expansions carried out for J = 6 which suffices to provide full double precision accuracy for |f| ≤ 1/50. Trigonometric series of this type can be conveniently summed using Clenshaw summation.

In order to solve the direct geodesic problem, it is necessary to find σ given s. Since the integrand in the distance integral is positive, this problem has a unique root, which may be found using Newton's method, noting that the required derivative is just the integrand of the distance integral. Oriani (1833) instead uses series reversion so that σ can be found without iteration; Helmert (1880) gives a similar series. The reverted series converges somewhat slower that the direct series and, if |f| > 1/100, Karney (2013，addenda) supplements the reverted series with one step of Newton's method to maintain accuracy. Vincenty (1975a) instead relies on a simpler (but slower) function iteration to solve for σ.

It is also possible to evaluate the integrals (4) and (5) by numerical quadrature (Saito 1970) (Saito 1979) (Sjöberg & Shirazian 2012) or to apply numerical techniques for the solution of the ordinary differential equations, Eqs. (2) (Kivioja 1971) (Thomas & Featherstone 2005) (Panou et al. 2013). Such techniques can be used for arbitrary flattening f. However, if f is small, e.g., |f| ≤ 1/50, they do not offer the speed and accuracy of the series expansions described above. Furthermore, for arbitrary f, the evaluation of the integrals in terms of elliptic integrals (see below) also provides a fast and accurate solution. On the other hand, Mathar (2007) has tackled the more complex problem of geodesics on the surface at a constant altitude, h, above the ellipsoid by solving the corresponding ordinary differential equations, Eqs. (2) with [ρ, ν] replaced by [ρ + h, ν + h].

A. M. Legendre

Arthur Cayley

Geodesics on an ellipsoid was an early application of elliptic integrals. In particular, Legendre (1811) writes the integrals, Eqs. (4) and (5), as

(6)${\color {white}.}\qquad \displaystyle {\frac {s}{b}}=E(\sigma ,ik),$

(7)${\color {white}.}\qquad {\begin{aligned}\lambda &=(1-f)\sin \alpha _{0}G(\sigma ,\cos ^{2}\alpha _{0},ik)\\&=\chi -{\frac {e'^{2}}{\sqrt {1+e'^{2}}}}\sin \alpha _{0}H(\sigma ,-e'^{2},ik),\\\end{aligned}}$

where

$\tan \chi ={\sqrt {\frac {1+e'^{2}}{1+k^{2}\sin ^{2}\sigma }}}\tan \omega ,$

and

${\begin{aligned}G(\phi ,\alpha ^{2},k)&=\int _{0}^{\phi }{\frac {\sqrt {1-k^{2}\sin ^{2}\theta }}{1-\alpha ^{2}\sin ^{2}\theta }}\,d\theta \\&={\frac {k^{2}}{\alpha ^{2}}}F(\phi ,k)+{\biggl (}1-{\frac {k^{2}}{\alpha ^{2}}}{\biggr )}\Pi (\phi ,\alpha ^{2},k),\\H(\phi ,\alpha ^{2},k)&=\int _{0}^{\phi }{\frac {\cos ^{2}\theta }{(1-\alpha ^{2}\sin ^{2}\theta ){\sqrt {1-k^{2}\sin ^{2}\theta }}}}\,d\theta \\&={\frac {1}{\alpha ^{2}}}F(\phi ,k)+{\biggl (}1-{\frac {1}{\alpha ^{2}}}{\biggr )}\Pi (\phi ,\alpha ^{2},k),\end{aligned}}$

and F(φ, k), E(φ, k), and Π(φ, α², k), are incomplete elliptic integrals in the notation of DLMF (2010，§19.2(ii)). The first formula for the longitude in Eq. (7) follows directly from the first form of Eq. (5). The second formula in Eq. (7), due to Cayley (1870), is more convenient for calculation since the elliptic integral appears in a small term. The equivalence of the two forms follows from DLMF (2010，Eq. (19.7.8)). Fast algorithms for computing elliptic integrals are given by Carlson (1995) in terms of symmetric elliptic integrals. Equation (6) is conveniently inverted using Newton's method. The use of elliptic integrals provides a good method of solving the geodesic problem for |f| > 1/50.

Solution of the direct problem

The basic strategy for solving the geodesic problems on the ellipsoid is to map the problem onto the auxiliary sphere by converting φ, λ, and s, to β, ω and σ, to solve the corresponding great-circle problem on the sphere, and to transfer the results back to the ellipsoid.

In implementing this program, we will frequently need to solve the "elementary" spherical triangle for NEP in Fig. 6 with P replaced by either A (subscript 1) or B (subscript 2). For this purpose, we can apply Napier's rules for quadrantal triangles to the triangle NEP on the auxiliary sphere which give

${\begin{aligned}\sin \alpha _{0}&=\sin \alpha \cos \beta =\tan \omega \cot \sigma ,\\\cos \sigma &=\cos \beta \cos \omega =\tan \alpha _{0}\cot \alpha ,\\\cos \alpha &=\cos \omega \cos \alpha _{0}=\cot \sigma \tan \beta ,\\\sin \beta &=\cos \alpha _{0}\sin \sigma =\cot \alpha \tan \omega ,\\\sin \omega &=\sin \sigma \sin \alpha =\tan \beta \tan \alpha _{0}.\end{aligned}}$

We can also stipulate that cosβ ≥ 0 and cosα₀ ≥ 0. Implementing this plan for the direct problem is straightforward. We are given φ₁, α₁, and s₁₂. From φ₁ we obtain β₁ (using the formula for the parametric latitude). We now solve the triangle problem with P = A and β₁ and α₁ given to find α₀, σ₁, and ω₁. Use the distance and longitude equations, Eqs. (4) and (5), together with the known value of λ₁, to find s₁ and λ₀. Determine s₂ = s₁ + s₁₂ and invert the distance equation to find σ₂. Solve the triangle problem with P = B and α₀ and σ₂ given to find β₂, ω₂, and α₂. Convert β₂ to φ₂ and substitute σ₂ and ω₂ into the longitude equation to give λ₂.

The overall method follows the procedure for solving the direct problem on a sphere. It is essentially the program laid out by Bessel (1825), Helmert (1880，§5.9), and most subsequent authors.

Intermediate points, way-points, on a geodesic can be found by holding φ₁ and α₁ fixed and solving the direct problem for several values of s₁₂. Once the first waypoint is found, only the last portion of the solution (starting with the determination of s₂) needs to be repeated for each new value of s₁₂.

Solution of the inverse problem

The ease with which the direct problem can be solved results from the fact that given φ₁ and α₁, we can immediately find α₀, the parameter in the distance and longitude integrals, Eqs. (4) and (5). In the case of the inverse problem, we are given λ₁₂, but we cannot easily relate this to the equivalent spherical angle ω₁₂ because α₀ is unknown. Thus, the solution of the problem requires that α₀ be found iteratively. Before tackling this, it is worth understanding better the behavior of geodesics, this time, keeping the starting point fixed and varying the azimuth.

Geodesics from a single point (f = 1/10, φ₁ = −30°)

Fig. 15. Geodesics, geodesic circles, and the cut locus.

Fig. 16. The geodesics shown on a plate carrée projection.

Fig. 17. λ₁₂ as a function of α₁ for φ₁ = −30° and φ₂ = 20°.

Suppose point A in the inverse problem has φ₁ = −30° and λ₁ = 0°. Fig. 15 shows geodesics (in blue) emanating A with α₁ a multiple of 15° up to the point at which they cease to be shortest paths. (The flattening has been increased to 1/10 in order to accentuate the ellipsoidal effects.) Also shown (in green) are curves of constant s₁₂, which are the geodesic circles centered A. Gauss (1828) showed that, on any surface, geodesics and geodesic circle intersect at right angles. The red line is the cut locus, the locus of points which have multiple (two in this case) shortest geodesics from A. On a sphere, the cut locus is a point. On an oblate ellipsoid (shown here), it is a segment of the circle of latitude centered on the point antipodal to A, φ = −φ₁. The longitudinal extent of cut locus is approximately λ₁₂ ∈ [π − f π cosφ₁, π + f π cosφ₁]. If A lies on the equator, φ₁ = 0, this relation is exact and as a consequence the equator is only a shortest geodesic if |λ₁₂| ≤ (1 − f)π. For a prolate ellipsoid, the cut locus is a segment of the anti-meridian centered on the point antipodal to A, λ₁₂ = π, and this means that meridional geodesics stop being shortest paths before the antipodal point is reached.

The solution of the inverse problem involves determining, for a given point B with latitude φ₂ and longitude λ₂ which blue and green curves it lies on; this determines α₁ and s₁₂ respectively. In Fig. 16, the ellipsoid has been "rolled out" onto a plate carrée projection. Suppose φ₂ = 20°, the green line in the figure. Then as α₁ is varied between 0° and 180°, the longitude at which the geodesic intersects φ = φ₂ varies between 0° and 180° (see Fig. 17). This behavior holds provided that |φ₂| ≤ |φ₁| (otherwise the geodesic does not reach φ₂ for some values of α₁). Thus, the inverse problem may be solved by determining the value α₁ which results in the given value of λ₁₂ when the geodesic intersects the circle φ = φ₂.

This suggests the following strategy for solving the inverse problem (Karney 2013). Assume that the points A and B satisfy

(8)${\color {white}.}\qquad \phi _{1}\leq 0,\quad \left|\phi _{2}\right|\leq \left|\phi _{1}\right|,\quad 0\leq \lambda _{12}\leq \pi .$

(There is no loss of generality in this assumption, since the symmetries of the problem can be used to generate any configuration of points from such configurations.)

1. First treat the "easy" cases, geodesics which lie on a meridian or the equator. Otherwise...
2. Guess a value of α₁.
3. Solve the so-called hybrid geodesic problem, given φ₁, φ₂, and α₁ find λ₁₂, s₁₂, and α₂, corresponding to the first intersection of the geodesic with the circle φ = φ₂.
4. Compare the resulting λ₁₂ with the desired value and adjust α₁ until the two values agree. This completes the solution.

Each of these steps requires some discussion.

1. For an oblate ellipsoid, the shortest geodesic lies on a meridian if either point lies on a pole or if λ₁₂ = 0 or ±π. The shortest geodesic follows the equator if φ₁ = φ₂ = 0 and |λ₁₂| ≤ (1 − f)π. For a prolate ellipsoid, the meridian is no longer the shortest geodesic if λ₁₂ = ±π and the points are close to antipodal (this will be discussed in the next section). There is no longitudinal restriction on equatorial geodesics.

2. In most cases a suitable starting value of α₁ is found by solving the spherical inverse problem

$\tan \alpha _{1}={\frac {\cos \beta _{2}\sin \omega _{12}}{\cos \beta _{1}\sin \beta _{2}-\sin \beta _{1}\cos \beta _{2}\cos \omega _{12}}},$

with ω₁₂ = λ₁₂. This may be a bad approximation if A and B are nearly antipodal (both the numerator and denominator in the formula above become small); however, this may not matter (depending on how step 4 is handled).

3. The solution of the hybrid geodesic problem is as follows. It starts the same way as the solution of the direct problem, solving the triangle NEP with P = A to find α₀, σ₁, ω₁, and λ₀. Now find α₂ from sinα₂ = sinα₀/cosβ₂, taking cosα₂ ≥ 0 (corresponding to the first, northward, crossing of the circle φ = φ₂). Next, σ₂ is given by tanσ₂ = tanβ₂/cosα₂ and ω₂ by tanω₂ = tanσ₂/sinα₀. Finally, use the distance and longitude equations, Eqs. (4) and (5), to find s₁₂ and λ₁₂.

4. In order to discuss how α₁ is updated, let us define the root-finding problem in more detail. The curve in Fig. 17 shows λ₁₂(α₁; φ₁, φ₂) where we regard φ₁ and φ₂ as parameters and α₁ as the independent variable. We seek the value of α₁ which is the root of

$g(\alpha _{1})\equiv \lambda _{12}(\alpha _{1};\phi _{1},\phi _{2})-\lambda _{12}=0,$

where g(0) ≤ 0 and g(π) ≥ 0. In fact, there is a unique root in the interval α₁ ∈ [0, π]. Any of a number of root-finding algorithms can be used to solve such an equation. Karney (2013) uses Newton's method, which requires a good starting guess; however it may be supplemented by a fail-safe method, such as the bisection method, to guarantee convergence.

F. R. Helmert

An alternative method for solving the inverse problem is given by Helmert (1880，§5.13). Let us rewrite the Eq. (5) as

${\begin{aligned}\lambda _{12}&=\omega _{12}-f\sin \alpha _{0}\int _{\sigma _{1}}^{\sigma _{2}}{\frac {2-f}{1+(1-f){\sqrt {1+k^{2}\sin ^{2}\sigma '}}}}\,d\sigma '\\&=\omega _{12}-f\sin \alpha _{0}I(\sigma _{1},\sigma _{2};\alpha _{0}).\end{aligned}}$

Helmert's method entails assuming that ω₁₂ = λ₁₂, solving the resulting problem on auxiliary sphere, and obtaining an updated estimate of ω₁₂ using

$\omega _{12}=\lambda _{12}+f\sin \alpha _{0}I(\sigma _{1},\sigma _{2};\alpha _{0}).$

This fixed point iteration is repeated until convergence. Rainsford (1955) advocates this method and Vincenty (1975a) adopted it in his solution of the inverse problem. The drawbacks of this method are that convergence is slower than obtained using Newton's method (as described above) and, more seriously, that the process fails to converge at all for nearly antipodal points. In a subsequent report, Vincenty (1975b) attempts to cure this defect; but he is only partially successful—the NGS (2012) implementation still includes Vincenty's fix still fails to converge in some cases. Lee (2011) has compared 17 methods for solving the inverse problem against the method given by Karney (2013).

The shortest distance returned by the solution of the inverse problem is (obviously) uniquely defined. However, if B lies on the cut locus of A there are multiple azimuths which yield the same shortest distance. Here is a catalog of those cases:

• φ₁ = −φ₂ (with neither point at a pole). If α₁ = α₂, the geodesic is unique. Otherwise there are two geodesics and the second one is obtained by interchanging α₁ and α₂. (This occurs when λ₁₂ ≈ ±π for oblate ellipsoids.)
• λ₁₂ = ±π (with neither point at a pole). If α₁ = 0 or ±π, the geodesic is unique. Otherwise there are two geodesics and the second one is obtained by negating α₁ and α₂. (This occurs when φ₁ + φ₂ ≈ 0 for prolate ellipsoids.)
• A and B are at opposite poles. There are infinitely many geodesics which can be generated by varying the azimuths so as to keep α₁ + α₂ constant. (For spheres, this prescription applies when A and B are antipodal.)

Differential behavior of geodesics

C. F. Gauss

E. B. Christoffel

Various problems involving geodesics require knowing their behavior when they are perturbed. This is useful in trigonometric adjustments (Ehlert 1993), determining the physical properties of signals which follow geodesics, etc. Consider a reference geodesic, parameterized by s the length from the northward equator crossing, and a second geodesic a small distance t(s) away from it. Gauss (1828) showed that t(s) obeys the Gauss-Jacobi equation

(9)${\color {white}.}\qquad \displaystyle {\frac {d^{2}t(s)}{ds^{2}}}=K(s)t(s),$

Fig. 18. Definition of reduced length and geodesic scale.

where K(s) is the Gaussian curvature at s. The solution may be expressed as the sum of two independent solutions

$t(s_{2})=Cm(s_{1},s_{2})+DM(s_{1},s_{2})$

where

${\begin{aligned}m(s_{1},s_{1})&=0,\quad \left.{\frac {dm(s_{1},s_{2})}{ds_{2}}}\right|_{s_{2}=s_{1}}=1,\\M(s_{1},s_{1})&=1,\quad \left.{\frac {dM(s_{1},s_{2})}{ds_{2}}}\right|_{s_{2}=s_{1}}=0.\end{aligned}}$

We shall abbreviate m(s₁, s₂) = m₁₂, the so-called reduced length, and M(s₁, s₂) = M₁₂, the geodesic scale. Their basic definitions are illustrated in Fig. 18. Christoffel (1869) made an extensive study of their properties. The reduced length obeys a reciprocity relation,

$m_{12}+m_{21}=0.$

Their derivatives are

${\begin{aligned}{\frac {dm_{12}}{ds_{2}}}&=M_{21},\\{\frac {dM_{12}}{ds_{2}}}&=-{\frac {1-M_{12}M_{21}}{m_{12}}}.\end{aligned}}$

Assuming that points 1, 2, and 3, lie on the same geodesic, then the following addition rules apply (Karney 2013),

${\begin{aligned}m_{13}&=m_{12}M_{23}+m_{23}M_{21},\\M_{13}&=M_{12}M_{23}-(1-M_{12}M_{21}){\frac {m_{23}}{m_{12}}},\\M_{31}&=M_{32}M_{21}-(1-M_{23}M_{32}){\frac {m_{12}}{m_{23}}}.\end{aligned}}$

The reduced length and the geodesic scale are components of the Jacobi field.

The Gaussian curvature for an ellipsoid of revolution is

$K={\frac {1}{\rho \nu }}={\frac {(1-e^{2}\sin ^{2}\phi )^{2}}{b^{2}}}={\frac {b^{2}}{a^{4}(1-e^{2}\cos ^{2}\beta )^{2}}}.$

Helmert (1880，Eq. (6.5.1.)) solved the Gauss-Jacobi equation for this case obtaining

${\begin{aligned}m_{12}/b&={\sqrt {1+k^{2}\sin ^{2}\sigma _{2}}}\,\cos \sigma _{1}\sin \sigma _{2}-{\sqrt {1+k^{2}\sin ^{2}\sigma _{1}}}\,\sin \sigma _{1}\cos \sigma _{2}\\&\quad -\cos \sigma _{1}\cos \sigma _{2}{\bigl (}J(\sigma _{2})-J(\sigma _{1}){\bigr )},\\M_{12}&=\cos \sigma _{1}\cos \sigma _{2}+{\frac {\sqrt {1+k^{2}\sin ^{2}\sigma _{2}}}{\sqrt {1+k^{2}\sin ^{2}\sigma _{1}}}}\sin \sigma _{1}\sin \sigma _{2}\\&\quad -{\frac {\sin \sigma _{1}\cos \sigma _{2}{\bigl (}J(\sigma _{2})-J(\sigma _{1}){\bigr )}}{\sqrt {1+k^{2}\sin ^{2}\sigma _{1}}}},\end{aligned}}$

where

${\begin{aligned}J(\sigma )&=\int _{0}^{\sigma }{\frac {k^{2}\sin ^{2}\sigma '}{\sqrt {1+k^{2}\sin ^{2}\sigma '}}}\,d\sigma '\\&=E(\sigma ,ik)-F(\sigma ,ik).\end{aligned}}$

As we see from Fig. 18 (top sub-figure), the separation of two geodesics starting at the same point with azimuths differing by dα₁ is m₁₂ dα₁. On a closed surface such as an ellipsoid, we expect m₁₂ to oscillate about zero. Indeed, if the starting point of a geodesic is a pole, φ₁ = ½π, then the reduced length is the radius of the circle of latitude, m₁₂ = a cosβ₂ = a sinσ₁₂. Similarly, for a meridional geodesic starting on the equator, φ₁ = α₁ = 0, we have M₁₂ = cosσ₁₂. In the typical case, these quantities oscillate with a period of about 2π in σ₁₂ and grow linearly with distance at a rate proportional to f. In trigonometric adjustments over small areas, it may be possible to approximate K(s) in Eq. (9) by a constant K. In this limit, the solutions for m₁₂ and M₁₂ are the same as for a sphere of radius 1/√K, namely,

$m_{12}=\sin({\sqrt {K}}s_{12})/{\sqrt {K}},\quad M_{12}=\cos({\sqrt {K}}s_{12}).$

To simplify the discussion of shortest paths in this paragraph we consider only geodesics with s₁₂ > 0. The point at which m₁₂ becomes zero is the point conjugate to the starting point. In order for a geodesic between A and B, of length s₁₂, to be a shortest path it must satisfy the Jacobi condition (Jacobi 1837) (Jacobi 1866，§6) (Forsyth 1927，§§26–27) (Bliss 1916), that there is no point conjugate to A between A and B. If this condition is not satisfied, then there is a nearby path (not necessarily a geodesic) which is shorter. Thus, the Jacobi condition is a local property of the geodesic and is only a necessary condition for the geodesic being a global shortest path. Necessary and sufficient conditions for a geodesic being the shortest path are:

• for an oblate ellipsoid, |σ₁₂| ≤ π;
• for a prolate ellipsoid, |λ₁₂| ≤ π, if α₀ ≠ 0; if α₀ = 0, the supplemental condition m₁₂ ≥ 0 is required if |λ₁₂| = π.

The latter condition above can be used to determine whether the shortest path is a meridian in the case of a prolate ellipsoid with |λ₁₂| = π. The derivative required to solve the inverse method using Newton's method, ∂λ₁₂(α₁; φ₁, φ₂) / ∂α₁, is given in terms of the reduced length (Karney 2013，Eq. (46)).

Geodesic map projections

Two map projections are defined in terms of geodesics. They are based on polar and rectangular geodesic coordinates on the surface (Gauss 1828). The polar coordinate system (r, θ) is centered on some point A. The coordinates of another point B are given by r = s₁₂ and θ = ½π − α₁ and these coordinates are used to find the projected coordinates on a plane map, x = r cosθ and y = r sinθ. The result is the familiar azimuthal equidistant projection; in the field of the differential geometry of surfaces, it is called the exponential map. Due to the basic properties of geodesics (Gauss 1828), lines of constant r and lines of constant θ intersect at right angles on the surface. The scale of the projection in the radial direction is unity, while the scale in the azimuthal direction is s₁₂/m₁₂.

The rectangular coordinate system (x, y) uses a reference geodesic defined by A and α₁ as the x axis. The point (x, y) is found by traveling a distance s₁₃ = x from A along the reference geodesic to an intermediate point C and then turning ½π counter-clockwise and traveling along a geodesic a distance s₃₂ = y. If A is on the equator and α₁ = ½π, this gives the equidistant cylindrical projection. If α₁ = 0, this gives the Cassini-Soldner projection. Cassini's map of France placed A at the Paris Observatory. Due to the basic properties of geodesics (Gauss 1828), lines of constant x and lines of constant y intersect at right angles on the surface. The scale of the projection in the y direction is unity, while the scale in the x direction is 1/M₃₂.

The gnomonic projection is a projection of the sphere where all geodesics (i.e., great circles) map to straight lines (making it a convenient aid to navigation). Such a projection is only possible for surfaces of constant Gaussian curvature (Beltrami 1865). Thus a projection in which geodesics map to straight lines is not possible for an ellipsoid. However, it is possible to construct an ellipsoidal gnomonic projection in which this property approximately holds (Karney 2013，§8). On the sphere, the gnomonic projection is the limit of a doubly azimuthal projection, a projection preserving the azimuths from two points A and B, as B approaches A. Carrying out this limit in the case of a general surface yields an azimuthal projection in which the distance from the center of projection is given by ρ = m₁₂/M₁₂. Even though geodesics are only approximately straight in this projection, all geodesics through the center of projection are straight. The projection can then be used to give an iterative but rapidly converging method of solving some problems involving geodesics, in particular, finding the intersection of two geodesics and finding the shortest path from a point to a geodesic.

The Hammer retroazimuthal projection is a variation of the azimuthal equidistant projection (Hammer 1910). A geodesic is constructed from a central point A to some other point B. The polar coordinates of the projection of B are r = s₁₂ and θ = ½π − α₂ (which depends on the azimuth at B, instead of at A). This can be used to determine the direction from an arbitrary point to some fixed center. Hinks (1929) suggested another application: if the central point A is a beacon, such as the Rugby Clock, then at an unknown location B the range and the bearing to A can be measured and the projection can be used to estimate the location of B.

Envelope of geodesics

Geodesics from a single point (f = 1/10, φ₁ = −30°)

Fig. 19. The envelope of geodesics from a point A at φ₁ = −30°.

Fig. 20. The four geodesics connecting A and a point B, φ₂ = 26°, λ₁₂ = 175°.

The geodesics from a particular point A if continued past the cut locus form an envelope illustrated in Fig. 19. Here the geodesics for which α₁ is a multiple of 3° are shown in light blue. (The geodesics are only shown for their first passage close to the antipodal point, not for subsequent ones.) Some geodesic circles are shown in green; these form cusps on the envelope. The cut locus is shown in red. The envelope is the locus of points which are conjugate to A; points on the envelope may be computed by finding the point at which m₁₂ = 0 on a geodesic (and Newton's method can be used to find this point). Jacobi (1891) calls this star-like figure produced by the envelope an astroid.

Outside the astroid two geodesics intersect at each point; thus there are two geodesics (with a length approximately half the circumference of the ellipsoid) between A and these points. This corresponds to the situation on the sphere where there are "short" and "long" routes on a great circle between two points. Inside the astroid four geodesics intersect at each point. Four such geodesics are shown in Fig. 20 where the geodesics are numbered in order of increasing length. (This figure uses the same position for A as Fig. 15 and is drawn in the same projection.) The two shorter geodesics are stable, i.e., m₁₂ > 0, so that there is no nearby path connecting the two points which is shorter; the other two are unstable. Only the shortest line (the first one) has σ₁₂ ≤ π. All the geodesics are tangent to the envelope which is shown in green in the figure. A similar set of geodesics for the WGS84 ellipsoid is given in this table (Karney 2011，Table 1):

Geodesics for φ₁ = −30°, φ₂ = 29.9°, λ₁₂ = 179.8° (WGS84)

No.	α1 (°)	α2 (°)	s12 (m)	σ12 (°)	m12 (m)
1	161.890524736	18.090737246	19989832.8276	179.894971388	57277.3769
2	30.945226882	149.089121757	20010185.1895	180.116378785	24240.7062
3	68.152072881	111.990398904	20011886.5543	180.267429871	−22649.2935
4	−81.075605986	−99.282176388	20049364.2525	180.630976969	−68796.1679

The approximate shape of the astroid is given by

$x^{2/3}+y^{2/3}=1$

or, in parametric form,

$x=\cos ^{3}\theta ,\quad y=\sin ^{3}\theta .$

The astroid is also the envelope of the family of lines

${\frac {x}{\cos \gamma }}+{\frac {y}{\sin \gamma }}=1,$

where γ is a parameter. (These are generated by the rod of the trammel of Archimedes.) This aids in finding a good starting guess for α₁ for Newton's method for in inverse problem in the case of nearly antipodal points (Karney 2013，§5).

The astroid is the (exterior) evolute of the geodesic circles centered at A. Likewise, the geodesic circles are involutes of the astroid.

Area of a geodesic polygon

A geodesic polygon is a polygon whose sides are geodesics. The area of such a polygon may be found by first computing the area between a geodesic segment and the equator, i.e., the area of the quadrilateral AFHB in Fig. 1 (Danielsen 1989). Once this area is known, the area of a polygon may be computed by summing the contributions from all the edges of the polygon.

Here we develop the formula for the area S₁₂ of AFHB following Sjöberg (2006). The area of any closed region of the ellipsoid is

$T=\int dT=\int {\frac {1}{K}}\cos \phi \,d\phi \,d\lambda ,$

where dT is an element of surface area and K is the Gaussian curvature. Now the Gauss–Bonnet theorem applied to a geodesic polygon states

$\Gamma =\int K\,dT=\int \cos \phi \,d\phi \,d\lambda ,$

where

$\Gamma =2\pi -\sum _{j}\theta _{j}$

is the geodesic excess and θ_j is the exterior angle at vertex j. Multiplying the equation for Γ by R₂², where R₂ is the authalic radius, and subtracting this from the equation for T gives

${\begin{aligned}T&=R_{2}^{2}\,\Gamma +\int {\biggl (}{\frac {1}{K}}-R_{2}^{2}{\biggr )}\cos \phi \,d\phi \,d\lambda \\&=R_{2}^{2}\,\Gamma +\int {\biggl (}{\frac {b^{2}}{(1-e^{2}\sin ^{2}\phi )^{2}}}-R_{2}^{2}{\biggr )}\cos \phi \,d\phi \,d\lambda ,\end{aligned}}$

where the value of K for an ellipsoid has been substituted. Applying this formula to the quadrilateral AFHB, noting that Γ = α₂ − α₁, and performing the integral over φ gives

$S_{12}=R_{2}^{2}(\alpha _{2}-\alpha _{1})+b^{2}\int _{\lambda _{1}}^{\lambda _{2}}{\biggl (}{\frac {1}{2(1-e^{2}\sin ^{2}\phi )}}+{\frac {\tanh ^{-1}(e\sin \phi )}{2e\sin \phi }}-{\frac {R_{2}^{2}}{b^{2}}}{\biggr )}\sin \phi \,d\lambda ,$

where the integral is over the geodesic line (so that φ is implicitly a function of λ). Converting this into an integral over σ, we obtain

$S_{12}=R_{2}^{2}E_{12}-e^{2}a^{2}\cos \alpha _{0}\sin \alpha _{0}\int _{\sigma _{1}}^{\sigma _{2}}{\frac {t(e'^{2})-t(k^{2}\sin ^{2}\sigma )}{e'^{2}-k^{2}\sin ^{2}\sigma }}{\frac {\sin \sigma }{2}}\,d\sigma ,$

where

$t(x)=1+x+{\sqrt {1+x}}{\frac {\sinh ^{-1}\!{\sqrt {x}}}{\sqrt {x}}},$

and the notation E₁₂ = α₂ − α₁ is used for the geodesic excess. The integral can be expressed as a series valid for small f (Danielsen 1989) (Karney 2013，§6 and addendum).

The area of a geodesic polygon is given by summing S₁₂ over its edges. This result holds provided that the polygon does not include a pole; if it does 2π R₂² must be added to the sum. If the edges are specified by their vertices, then a convenient expression for E₁₂ is

$\tan {\frac {E_{12}}{2}}={\frac {\sin {\tfrac {1}{2}}(\beta _{2}+\beta _{1})}{\cos {\tfrac {1}{2}}(\beta _{2}-\beta _{1})}}\tan {\frac {\omega _{12}}{2}}.$

This result follows from one of Napier's analogies.

Software implementations

An implementation of Vincenty's algorithm in Fortran is provided by NGS (2012). Version 3.0 includes Vincenty's treatment of nearly antipodal points (Vincenty 1975b). Vincenty's original formulas are used in many geographic information systems. Except for nearly antipodal points (where the inverse method fails to converge), this method is accurate to about 0.1 mm for the WGS84 ellipsoid (Karney 2011，§9).

The algorithms given in Karney (2013) are included in GeographicLib (Karney 2014). These are accurate to about 15 nanometers for the WGS84 ellipsoid. Implementations in several languages (C++, C, Fortran, Java, JavaScript, Python, Matlab, and Maxima) are provided. In addition to solving the basic geodesic problem, this library can return m₁₂, M₁₂, M₂₁, and S₁₂. The library includes a command-line utility, GeodSolve, for geodesic calculations. As of version 4.9.1, the PROJ.4 library for cartographic projections uses the C implementation for geodesic calculations. This is exposed in the command-line utility, geod, and in the library itself.

The solution of the geodesic problems in terms of elliptic integrals is included in GeographicLib (in C++ only), e.g., via the -E option to GeodSolve. This method of solution is about 2–3 times slower than using series expansions; however it provides accurate solutions for ellipsoids of revolution with b/a ∈ [0.01, 100] (Karney 2013，addenda).

Geodesics on a triaxial ellipsoid

Solving the geodesic problem for an ellipsoid of revolution is, from the mathematical point of view, relatively simple: because of symmetry, geodesics have a constant of the motion, given by Clairaut's relation allowing the problem to be reduced to quadrature. By the early 19th century (with the work of Legendre, Oriani, Bessel, et al.), there was a complete understanding of the properties of geodesics on an ellipsoid of revolution.

On the other hand, geodesics on a triaxial ellipsoid (with 3 unequal axes) have no obvious constant of the motion and thus represented a challenging "unsolved" problem in the first half of the 19th century. In a remarkable paper, Jacobi (1839) discovered a constant of the motion allowing this problem to be reduced to quadrature also (Klingenberg 1982，§3.5).

Triaxial coordinate systems

Gaspard Monge

Charles Dupin

The key to the solution is expressing the problem in the "right" coordinate system. Consider the ellipsoid defined by

$h={\frac {X^{2}}{a^{2}}}+{\frac {Y^{2}}{b^{2}}}+{\frac {Z^{2}}{c^{2}}}=1,$

where (X,Y,Z) are Cartesian coordinates centered on the ellipsoid and, without loss of generality, a ≥ b ≥ c > 0. A point on the surface is specified by a latitude and longitude. The geographical latitude and longitude (φ, λ) are defined by

${\frac {\nabla h}{\left|\nabla h\right|}}=\left({\begin{array}{c}\cos \phi \cos \lambda \\\cos \phi \sin \lambda \\\sin \phi \end{array}}\right).$

The parametric latitude and longitude (φ′, λ′) are defined by

${\begin{aligned}X&=a\cos \phi '\cos \lambda ',\\Y&=b\cos \phi '\sin \lambda ',\\Z&=c\sin \phi '.\end{aligned}}$

Jacobi (1866，§§26–27) employed the ellipsoidal latitude and longitude (β, ω) defined by

Fig. 21. Ellipsoidal coordinates.

${\begin{aligned}X&=a\cos \omega {\frac {\sqrt {a^{2}-b^{2}\sin ^{2}\beta -c^{2}\cos ^{2}\beta }}{\sqrt {a^{2}-c^{2}}}},\\Y&=b\cos \beta \sin \omega ,\\Z&=c\sin \beta {\frac {\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega -c^{2}}}{\sqrt {a^{2}-c^{2}}}}.\end{aligned}}$

In the limit b → a, β becomes the parametric latitude for an oblate ellipsoid, so the use of the symbol β is consistent with the previous sections. However, ω is different from the spherical longitude defined above.

Grid lines of constant β (in blue) and ω (in green) are given in Fig. 21. In contrast to (φ, λ) and (φ′, λ′), (β, ω) is an orthogonal coordinate system: the grid lines intersect at right angles. The principal sections of the ellipsoid, defined by X = 0 and Z = 0 are shown in red. The third principal section, Y = 0, is covered by the lines β = ±90° and ω = 0° or ±180°. These lines meet at four umbilical points (two of which are visible in this figure) where the principal radii of curvature are equal. Here and in the other figures in this section the parameters of the ellipsoid are a:b:c = 1.01:1:0.8, and it is viewed in an orthographic projection from a point above φ = 40°, λ = 30°.

The grid lines of the ellipsoidal coordinates may be interpreted in three different ways

1. They are "lines of curvature" on the ellipsoid, i.e., they are parallel to the directions of principal curvature (Monge 1796).
2. They are also intersections of the ellipsoid with confocal systems of hyperboloids of one and two sheets (Dupin 1813，Part 5).
3. Finally they are geodesic ellipses and hyperbolas defined using two adjacent umbilical points (Hilbert & Cohn-Vossen 1952，第188頁). For example, the lines of constant β in Fig. 21 can be generated with the familiar string construction for ellipses with the ends of the string pinned to the two umbilical points.

Conversions between these three types of latitudes and longitudes and the Cartesian coordinates are simple algebraic exercises.

The element of length on the ellipsoid in ellipsoidal coordinates is given by

${\begin{aligned}{\frac {ds^{2}}{(a^{2}-b^{2})\sin ^{2}\omega +(b^{2}-c^{2})\cos ^{2}\beta }}&={\frac {b^{2}\sin ^{2}\beta +c^{2}\cos ^{2}\beta }{a^{2}-b^{2}\sin ^{2}\beta -c^{2}\cos ^{2}\beta }}d\beta ^{2}\\&\qquad +{\frac {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega }{a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega -c^{2}}}d\omega ^{2}\end{aligned}}$

and the differential equations for a geodesic are

${\begin{aligned}{\frac {d\beta }{ds}}&={\frac {1}{\sqrt {(a^{2}-b^{2})\sin ^{2}\omega +(b^{2}-c^{2})\cos ^{2}\beta }}}{\frac {\sqrt {a^{2}-b^{2}\sin ^{2}\beta -c^{2}\cos ^{2}\beta }}{\sqrt {b^{2}\sin ^{2}\beta +c^{2}\cos ^{2}\beta }}}\cos \alpha ,\\{\frac {d\omega }{ds}}&={\frac {1}{\sqrt {(a^{2}-b^{2})\sin ^{2}\omega +(b^{2}-c^{2})\cos ^{2}\beta }}}{\frac {\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega -c^{2}}}{\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega }}}\sin \alpha ,\\{\frac {d\alpha }{ds}}&={\frac {1}{((a^{2}-b^{2})\sin ^{2}\omega +(b^{2}-c^{2})\cos ^{2}\beta )^{3/2}}}\times \\&\quad {\biggl (}{\frac {(a^{2}-b^{2})\cos \omega \sin \omega {\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega -c^{2}}}}{\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega }}}\cos \alpha \\&\qquad +{\frac {(b^{2}-c^{2})\cos \beta \sin \beta {\sqrt {a^{2}-b^{2}\sin ^{2}\beta -c^{2}\cos ^{2}\beta }}}{\sqrt {b^{2}\sin ^{2}\beta +c^{2}\cos ^{2}\beta }}}\sin \alpha {\biggr )}.\end{aligned}}$

Jacobi's solution

C. G. J. Jacobi

Joseph Liouville

J. G. Darboux

Jacobi showed that the geodesic equations, expressed in ellipsoidal coordinates, are separable. Here is how he recounted his discovery to his friend and neighbor Bessel (Jacobi 1839，Letter to Bessel),

The day before yesterday, I reduced to quadrature the problem of geodesic lines on an ellipsoid with three unequal axes. They are the simplest formulas in the world, Abelian integrals, which become the well known elliptic integrals if 2 axes are set equal.

Königsberg, 28th Dec. '38.

The solution given by Jacobi (Jacobi 1839) (Jacobi 1866，§28) is

${\begin{aligned}\delta &=\int {\frac {{\sqrt {b^{2}\sin ^{2}\beta +c^{2}\cos ^{2}\beta }}\,d\beta }{{\sqrt {a^{2}-b^{2}\sin ^{2}\beta -c^{2}\cos ^{2}\beta }}{\sqrt {(b^{2}-c^{2})\cos ^{2}\beta -\gamma }}}}\\&\quad -\int {\frac {{\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega }}\,d\omega }{{\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega -c^{2}}}{\sqrt {(a^{2}-b^{2})\sin ^{2}\omega +\gamma }}}}.\end{aligned}}$

As Jacobi notes "a function of the angle β equals a function of the angle ω. These two functions are just Abelian integrals..." Two constants δ and γ appear in the solution. Typically δ is zero if the lower limits of the integrals are taken to be the starting point of the geodesic and the direction of the geodesics is determined by γ. However, for geodesics that start at an umbilical points, we have γ = 0 and δ determines the direction at the umbilical point. The constant γ may be expressed as

$\gamma =(b^{2}-c^{2})\cos ^{2}\beta \sin ^{2}\alpha -(a^{2}-b^{2})\sin ^{2}\omega \cos ^{2}\alpha ,$

where α is the angle the geodesic makes with lines of constant ω. In the limit b → a, this reduces to sinα cosβ = const., the familiar Clairaut relation. A nice derivation of Jacobi's result is given by Darboux (1894，§§583–584) where he gives the solution found by Liouville (1846) for general quadratic surfaces. In this formulation, the distance along the geodesic, s, is found using

${\begin{aligned}{\frac {ds}{(a^{2}-b^{2})\sin ^{2}\omega +(b^{2}-c^{2})\cos ^{2}\beta }}&={\frac {{\sqrt {b^{2}\sin ^{2}\beta +c^{2}\cos ^{2}\beta }}\,d\beta }{{\sqrt {a^{2}-b^{2}\sin ^{2}\beta -c^{2}\cos ^{2}\beta }}{\sqrt {(b^{2}-c^{2})\cos ^{2}\beta -\gamma }}}}\\&={\frac {{\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega }}\,d\omega }{{\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega -c^{2}}}{\sqrt {(a^{2}-b^{2})\sin ^{2}\omega +\gamma }}}}.\end{aligned}}$

An alternative expression for the distance is

${\begin{aligned}ds&={\frac {{\sqrt {b^{2}\sin ^{2}\beta +c^{2}\cos ^{2}\beta }}{\sqrt {(b^{2}-c^{2})\cos ^{2}\beta -\gamma }}\,d\beta }{\sqrt {a^{2}-b^{2}\sin ^{2}\beta -c^{2}\cos ^{2}\beta }}}\\&\quad {}+{\frac {{\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega }}{\sqrt {(a^{2}-b^{2})\sin ^{2}\omega +\gamma }}\,d\omega }{\sqrt {a^{2}\sin ^{2}\omega +b^{2}\cos ^{2}\omega -c^{2}}}}.\end{aligned}}$

Survey of triaxial geodesics

Circumpolar geodesics, ω₁ = 0°, α₁ = 90°.

Fig. 22. β₁ = 45.1°.

Fig. 23. β₁ = 87.48°.

On a triaxial ellipsoid, there are only 3 simple closed geodesics, the three principal sections of the ellipsoid given by X = 0, Y = 0, and Z = 0. To survey the other geodesics, it is convenient to consider geodesics which intersect the middle principal section, Y = 0, at right angles. Such geodesics are shown in Figs. 22–26, which use the same ellipsoid parameters and the same viewing direction as Fig. 21. In addition, the three principal ellipses are shown in red in each of these figures.

If the starting point is β₁ ∈ (−90°, 90°), ω₁ = 0, and α₁ = 90°, then γ > 0 and the geodesic encircles the ellipsoid in a "circumpolar" sense. The geodesic oscillates north and south of the equator; on each oscillation it completes slightly less that a full circuit around the ellipsoid resulting, in the typical case, in the geodesic filling the area bounded by the two latitude lines β = ±β₁. Two examples are given in Figs. 22 and 23. Figure 22 shows practically the same behavior as for an oblate ellipsoid of revolution (because a ≈ b); compare to Fig. 11. However, if the starting point is at a higher latitude (Fig. 22) the distortions resulting from a ≠ b are evident. All tangents to a circumpolar geodesic touch the confocal single-sheeted hyperboloid which intersects the ellipsoid at β = β₁ (Chasles 1846) (Hilbert & Cohn-Vossen 1952，第223–224頁).

Transpolar geodesics, β₁ = 90°, α₁ = 180°.

Fig. 24. ω₁ = 39.9°.

Fig. 25. ω₁ = 9.966°.

If the starting point is β₁ = 90°, ω₁ ∈ (0°, 180°), and α₁ = 180°, then γ < 0 and the geodesic encircles the ellipsoid in a "transpolar" sense. The geodesic oscillates east and west of the ellipse X = 0; on each oscillation it completes slightly more that a full circuit around the ellipsoid resulting, in the typical case, in the geodesic filling the area bounded by the two longitude lines ω = ω₁ and ω = 180° − ω₁. If a = b, all meridians are geodesics; the effect of a ≠ b causes such geodesics to oscillate east and west. Two examples are given in Figs. 24 and 25. The constriction of the geodesic near the pole disappears in the limit b → c; in this case, the ellipsoid becomes a prolate ellipsoid and Fig. 24 would resemble Fig. 12 (rotated on its side). All tangents to a transpolar geodesic touch the confocal double-sheeted hyperboloid which intersects the ellipsoid at ω = ω₁.

Fig. 26. An umbilical geodesic, β₁ = 90°, ω₁ = 0°, α₁ = 135°.

If the starting point is β₁ = 90°, ω₁ = 0° (an umbilical point), and α₁ = 135° (the geodesic leaves the ellipse Y = 0 at right angles), then γ = 0 and the geodesic repeatedly intersects the opposite umbilical point and returns to its starting point. However, on each circuit the angle at which it intersects Y = 0 becomes closer to 0° or 180° so that asymptotically the geodesic lies on the ellipse Y = 0 (Hart 1849) (Arnold 1989，第265頁). This is shown in Fig. 26. Note that a single geodesic does not fill an area on the ellipsoid. All tangents to umbilical geodesics touch the confocal hyperbola which intersects the ellipsoid at the umbilic points.

Umbilical geodesic enjoy several interesting properties.

• Through any point on the ellipsoid, there are two umbilical geodesics.
• The geodesic distance between opposite umbilical points is the same regardless of the initial direction of the geodesic.
• Whereas the closed geodesics on the ellipses X = 0 and Z = 0 are stable (an geodesic initially close to and nearly parallel to the ellipse remains close to the ellipse), the closed geodesic on the ellipse Y = 0, which goes through all 4 umbilical points, is exponentially unstable. If it is perturbed, it will swing out of the plane Y = 0 and flip around before returning to close to the plane. (This behavior may repeat depending on the nature of the initial perturbation.)

If the starting point A of a geodesic is not an umbilical point, then its envelope is an astroid with two cusps lying on β = −β₁ and the other two on ω = ω₁ + π (Sinclair 2003). The cut locus for A is the portion of the line β = −β₁ between the cusps (Itoh & Kiyohara 2004).

(Panou 2013) gives a method for solving the inverse problem for a triaxial ellipsoid by directly integrating the system of ordinary differential equations for a geodesic. (Thus, it does not utilize Jacobi's solution.)

Applications

Karl Weierstrass

Henri Poincaré

The direct and inverse geodesic problems no longer play the central role in geodesy that they once did. Instead of solving adjustment of geodetic networks as a two-dimensional problem in spheroidal trigonometry, these problem are now solved by three-dimensional methods (Vincenty & Bowring 1978). Nevertheless, terrestrial geodesics still play an important role in several areas:

• for measuring distances and areas in geographic information systems;
• the definition of maritime boundaries (UNCLOS 2006);
• in the rules of the Federal Aviation Administration for area navigation (RNAV 2007);
• the method of measuring distances in the FAI Sporting Code (FAI 2013).

By the principle of least action, many problems in physics can be formulated as a variational problem similar to that for geodesics. Indeed, the geodesic problem is equivalent to the motion of a particle constrained to move on the surface, but otherwise subject to no forces (Laplace 1799a) (Hilbert & Cohn-Vossen 1952，第222頁). For this reason, geodesics on simple surfaces such as ellipsoids of revolution or triaxial ellipsoids are frequently used as "test cases" for exploring new methods. Examples include:

• the development of elliptic integrals (Legendre 1811) and elliptic functions (Weierstrass 1861);
• the development of differential geometry (Gauss 1828) (Christoffel 1869);
• methods for solving systems of differential equations by a change of independent variables (Jacobi 1839);
• the study of caustics (Jacobi 1891);
• investigations into the number and stability of periodic orbits (Poincaré 1905);
• in the limit c → 0, geodesics on a triaxial ellipsoid reduce to a case of dynamical billiards;
• extensions to an arbitrary number of dimensions (Knörrer 1980);
• geodesic flow on a surface (Berger 2010，Chap. 12).

See also

• Geographical distance
• Great-circle navigation
• Geodesics
• Geodesy
• Meridian arc
• Rhumb line
• Vincenty's formulae

References

• Arnold, V. I. Mathematical Methods of Classical Mechanics. Translated by K. Vogtmann & A. Weinstein 2nd. Springer-Verlag. 1989. ISBN 978-0-387-96890-2. OCLC 4037141. 
• Bagratuni, G. V. Course in Spheroidal Geodesy (PDF). 1967 [1962]. OCLC 6150611. Translation from Russian of Курс сфероидической геодезии (Moscow, 1962) by U.S. Air Force (FTD-MT-64-390) 
• doi:10.1007/BF03198517
  
• Berger, M. Geometry Revealed. Translated by L. J. Senechal. Springer. 2010. ISBN 978-3-540-70996-1. doi:10.1007/978-3-540-70997-8. 
• Bessel, F. W. . . Translated by C. F. F. Karney & R. E. Deakin. The calculation of longitude and latitude from geodesic measurements. Astronomische Nachrichten. 2010, 331 (8): 852–861 [1825]. arXiv:0908.1824 . doi:10.1002/asna.201011352. English translation of Astron. Nachr. 4, 241–254 (1825). Errata. 
• doi:10.1002/asna.18270051202
  
• doi:10.1090/S0002-9947-1916-1501037-4
  
• Bomford, G. Geodesy. Oxford: Clarendon. 1952. OCLC 1396190. 
• Borre, K.; Strang, W. G. Algorithms for Global Positioning. Wellesley-Cambridge Press. 2012. ISBN 978-0-9802327-3-8. OCLC 795014501. Chapter 11, Geometry of the Ellipsoid. 
• doi:10.1007/BF02198293
  
• Casper, P. W.; Bent, R. B. The effect of the Earth's oblate spheroid shape on the accuracy of a time-of-arrival lightning ground strike locating system (PDF). 1991. in Proceedings 1991 International Aerospace and Ground Conference on Lightning and Static Electricity, (Vol. 2). 
• Cassini, J. De la carte de la France et de la perpendiculaire a la méridienne de Paris [The map of France and the perpendicular to the meridian of Paris]. Mémoires de l'Académie Royale des Sciences de Paris 1733. 1735: 389–405 （French）.  引文格式1维护：未识别语文类型 (link)
• Cayley, A. On the geodesic lines on an oblate spheroid. Philosophical Magazine (4th ser.). 1870, 40: 329–340. doi:10.1080/14786447008640411 (不活跃 2015-05-11). 
• Chasles, M. Sur les lignes géodésiques et les lignes de courbure des surfaces du second degré [Geodesic lines and the lines of curvature of the surfaces of the second degree]. Journal de Mathématiques Pures et Appliquées. 1846, 11: 5–20 （French）.  引文格式1维护：未识别语文类型 (link)
• Christoffel, E. B. Allgemeine Theorie der geodätischen Dreiecke [General theory of geodesic triangles]. Abhandlungen Königlichen Akademie der Wissenschaft zu Berlin. 1869: 119–176 （German）.  引文格式1维护：未识别语文类型 (link)
• Clairaut, A. C. Détermination géometrique de la perpendiculaire à la méridienne tracée par M. Cassini [Geometrical determination of the perpendicular to the meridian drawn by Jacques Cassini]. Mémoires de l'Académie Royale des Sciences de Paris 1733. 1735: 406–416 （French）.  引文格式1维护：未识别语文类型 (link)
• doi:10.1179/003962689791474267
  
• Darboux, J. G. Leçons sur la théorie générale des surfaces [Lessons on the general theory of surfaces] 3. Paris: Gauthier-Villars. 1894. OCLC 8566228 （French）. PDF.  引文格式1维护：未识别语文类型 (link)
• DLMF. Olver, F. W. J.; Lozier, D. W.; Boisvert, R. F.; Clark, C. W. , 编. NIST Handbook of Mathematical Functions. Cambridge Univ. Press. 2010. ISBN 978-0-521-19225-5. MR 2723248. 
• Dupin, P. C. F. Développements de Géométrie [Developments in geometry]. Paris: Courcier. 1813. OCLC 560800801 （French）.  引文格式1维护：未识别语文类型 (link)
• Ehlert, D. Methoden der ellipsoidischen Dreiecksberechnung [Methods for ellipsoidal triangulatioin] (技术报告). Reihe B: Angewandte Geodäsie, Heft Nr. 292. Deutsche Geodätische Kommission. 1993. OCLC 257615376 （German）.  引文格式1维护：未识别语文类型 (link)
• Euler, L. Élémens de la trigonométrie sphéroïdique tirés de la méthode des plus grands et plus petits [Elements of spheroidal trigonometry taken from the method of maxima and minima]. Mémoires de l'Académie Royale des Sciences de Berlin 1753. 1755, 9: 258–293 （French）. Figures.  引文格式1维护：未识别语文类型 (link)
• FAI. FAI Sporting Code (技术报告). Lausanne, Switzerland: Fédération Aéronautique Internationale. 2013. Section 7.3.1.1. 
• Forsyth, A. R. Geodesics on an oblate spheroid. Messenger of Mathematics. 1896, 25: 81–124. PDF. 
• Forsyth, A. R. Calculus of Variations. Cambridge Univ. Press. 1927. ISBN 978-1-107-64083-2. OCLC 250050479. 
• Gauss, C. F. General Investigations of Curved Surfaces of 1827 and 1825. Translated by J. C. Morehead and A. M. Hiltebeitel. Princeton Univ. Lib. 1902 [1828]. OCLC 7824448. PDF. English translation of Disquisitiones generales circa superficies curvas (Dieterich, Göttingen, 1828). 
• Halphen, G. H. Traité des Fonctions Elliptiques et de leurs Applications [A Treatise on Elliptic Functions and their Applications] 2. Gauthier-Villars. 1888. OCLC 25356730 （French）. Chapter 6. PDF.  引文格式1维护：未识别语文类型 (link)
• Hammer, E. Gegenazimutale Projektion [Retroazimuthal projection]. Petermanns Geographische Mitteilungen. 1910, 56 (3): 153–155 + plate （German）.  引文格式1维护：未识别语文类型 (link)
• Hansen, P. A. Geodätische Untersuchungen [Geodetic investigations]. Leipsig: Hirzel. 1865. OCLC 7687476 （German）.  引文格式1维护：未识别语文类型 (link)
• Hart, A. S. Geometrical demonstration of some properties of geodesic lines. Cambridge and Dublin Mathematical Journal. 1849, 4: 80–84. 
• Helmert, F. R. Mathematical and Physical Theories of Higher Geodesy 1. St. Louis: Aeronautical Chart and Information Center. 1964 [1880]. OCLC 17273288. English translation of Die Mathematischen und Physikalischen Theorieen der Höheren Geodäsie, Vol. 1 (Teubner, Leipzig, 1880). 
• Hilbert, D.; Cohn-Vossen, S. Geometry and the Imagination. Translated by P. Nemenyi. New York: Chelsea. 1952. OCLC 301610346. 
• doi:10.2307/1784715
  
• Hutton, C. A Course of Mathematics in Three Volumes Composed for the Use of the Royal Military Academy. London. 1811: 115. OCLC 18031510. 
• doi:10.1007/s00229-004-0455-z
  
• doi:10.1080/14786442608674069
  
• doi:10.1515/crll.1837.17.68
  
• doi:10.1515/crll.1839.19.309
  
• doi:10.1002/asna.18550411401
  
• Jacobi, C. G. J. A. Clebsch , 编. Lectures on Dynamics. Translated by K. Balagangadharan. New Delhi: Hindustan Book Agency. 2009 [1866]. ISBN 978-81-85931-91-3. MR 2569315. OCLC 440645889. English translation of Vorlesungen über Dynamik (Reimer, Berlin, 1866). Errata. 
• Jacobi, C. G. J. Über die Curve, welche alle von einem Punkte ausgehenden geodätischen Linien eines Rotationsellipsoides berührt [The envelope of geodesic lines emanating from a single point on an ellipsoid]. K. T. W. Weierstrass (editor) (编). Jacobi's Gesammelte Werke 7. Berlin: Reimer: 72–87. 1891. OCLC 630416023 （German）. Op. post., completed by F. H. A. Wangerin. PDF.  引文格式1维护：未识别语文类型 (link)
• Jekeli, C., Geometric Reference Systems in Geodesy, Ohio State Univ., 2012 
• Karney, C. F. F. GeographicLib. Version 2009-03. 2009. The first implementation of geodesic routines in Geographiclib. 
• Karney, C. F. F. Geodesics on an ellipsoid of revolution. 2011. arXiv:1102.1215v1  [physics.geo-ph]. Errata. 
• doi:10.1007/s00190-012-0578-z
  
• Karney, C. F. F. GeographicLib. Version 1.38. 2014. 
• doi:10.1109/TAP.1986.1143838
  
• doi:10.1007/BF02521679
  
• Klingenberg, W. P. A. Riemannian Geometry. de Gruyer. 1982. ISBN 978-3-11-008673-7. MR 0666697. OCLC 8476832. 
• doi:10.1007/BF01390041
  
• Krakiwsky, E. J.; Thomson, D. B., Geodetic position computations (PDF), Dept. of Geodesy and Geomatics Engineering, Lecture Notes (39), Fredericton, N.B.: Univ. of New Brunswick, 1974, Bibcode:1974gpc..book.....K 
• Kummell, C. H. Alignment of curves on any surface, with special application to the ellipsoid. Bulletin of the Philosophical Society of Washington. 1883, 6: 123–132. PDF. 
• Laplace, P. S. Treatise on Celestial Mechanics 1. Translated by N. Bowditch. Boston: Hillard, Gray, Little, & Wilkins. 1829 [1799a]. OCLC 1294937. Book 1, § 8. 
• Laplace, P. S. Traité de Mécanique Céleste [Treatise on Celestial Mechanics] 2. Paris: Crapelet. 1799b: 112. OCLC 25448952 （French）.  引文格式1维护：未识别语文类型 (link)
• doi:10.7848/ksgpc.2011.29.4.329
  
• Legendre, A. M. Analyse des triangles tracées sur la surface d'un sphéroïde [Analysis of spheroidal triangles]. Mémoires de l'Institut National de France. 1806, (1st semester): 130–161 （French）.  引文格式1维护：未识别语文类型 (link)
• Legendre, A. M. Exercices de Calcul Intégral sur Divers Ordres de Transcendantes et sur les Quadratures [Exercises in Integral Calculus]. Paris: Courcier. 1811. OCLC 312469983 （French）.  引文格式1维护：未识别语文类型 (link)
• Levallois, J. J.; Dupuy, M. Note sur le Calcul des Grandes Géodésiques (技术报告). Paris: Institut Géographique National. 1952. Chapter 2. 
• Liouville, J. Sur quelques cas particuliers où les équations du mouvement d'un point matériel peuvent s'intégrer [Special cases where the equations of motion are integrable]. Journal de Mathématiques Pures et Appliquées. 1846, 11: 345–378 （French）.  引文格式1维护：未识别语文类型 (link)
• Lyusternik, L. Shortest Paths: Variational Problems. Popular Lectures in Mathematics 13. Translated by P. Collins and R. B. Brown. New York: Macmillan. 1964. MR 0178386. OCLC 1048605. Translation from Russian of Кратчайшие Линии: Вариационные Задачи (Moscow, 1955). 
• Lyusternik, L.; Schnirelmann, L. Sur le problème de trois géodésiques fermées sur les surfaces de genre 0 [The problem of three closed geodesics on surfaces of genus 0]. Comptes Rendus de l'Académie des Sciences de Paris. 1929, 189: 269–271 （French）.  引文格式1维护：未识别语文类型 (link)
• doi:10.1002/asna.18550422201
  
• Mathar, R. J. Geodetic line at constant altitude above the ellipsoid. 2007. arXiv:0711.0642  [math.MG]. 
• Monge, G. Sur les lignes de courbure de la surface de l'ellipsoïde [On the lines of curvature on the surface of the ellipsoid]. J. Liouville (editor) (编). Application de l'Analyse à la Géometrie 5th. Paris: Bachelier: 139–160. 1850 [1796]. OCLC 2829112 （French）. Figures.  引文格式1维护：未识别语文类型 (link)
• doi:10.1175/1520-0485(1989)019.3C1765:GOWAAM.3E2.0.CO;2
  
• National Geodetic Survey. Geodesic Utilities: Inverse and Forward. Version 3.0. 2012. 
• Newton, I. The Mathematical Principles of Natural Philosophy. Translated by A. Motte. New York: Adee. 1848 [1687]. Book 3, Proposition 19, Problem 3, pp. 405–409. 
• Oriani, B. Elementi di trigonometria sferoidica, Pt. 1 [Elements of spheroidal trigonometry]. Memorie dell'Istituto Nazionale Italiano. 1806, 1 (1): 118–198 （Italian）.  引文格式1维护：未识别语文类型 (link)
• Oriani, B. Elementi di trigonometria sferoidica, Pt. 2 [Elements of spheroidal trigonometry]. Memorie dell'Istituto Nazionale Italiano. 1808, 2 (1): 1–58 （Italian）.  引文格式1维护：未识别语文类型 (link)
• Oriani, B. Elementi di trigonometria sferoidica, Pt. 3 [Elements of spheroidal trigonometry]. Memorie dell'Istituto Nazionale Italiano. 1810, 2 (2): 1–58 （Italian）.  引文格式1维护：未识别语文类型 (link)
• doi:10.1002/asna.18260043201
  
• Oriani, B. Nota aggiunta agli elementi della trigonometria sferoidica [Note added to the elements of spheroidal trigonometry]. Memorie dell'Imperiale Regio Istituto del Regno Lombardo-Veneto. 1833, 4: 325–331 （Italian）.  引文格式1维护：未识别语文类型 (link)
• doi:10.2478/jogs-2013-0007
  
• doi:10.2478/jogs-2013-0028
  
• Pittman, M. E. Precision direct and inverse solutions of the geodesic. Surveying and Mapping. 1986, 46 (1): 47–54. 
• doi:10.2307/1986219
  
• doi:10.1007/BF02527187
  
• Rapp, R. H., Geometric geodesy, part I, Ohio State Univ., 1991 
• Rapp, R. H., Geometric geodesy, part II, Ohio State Univ., 1993 
• RNAV. Order 8260.54A, The United States Standard for Area Navigation (PDF) (技术报告). Washington, D.C.: U.S. Federal Aviation Administration. 2007. Appendix 2. 
• doi:10.1179/003962609X451663
  
• doi:10.1007/BF02522166
  
• doi:10.1007/BF02521087
  
• doi:10.1080/10586458.2003.10504515
  
• doi:10.1179/003962606780732100
  
• doi:10.1061/(ASCE)SU.1943-5428.0000061
  
• doi:10.1061/(ASCE)0733-9453(2005)131:1(20)
  
• Thomas, P. D. Spheroidal Geodesics, Reference Systems, & Local Geometry (技术报告). U.S. Naval Oceanographic Office. 1970. SP-138. 
• UNCLOS. A Manual on Technical Aspects of the United Nations Convention on the Law of the Sea, 1982 (PDF) (技术报告) 4th. Monaco: International Hydrographic Bureau. 2006. 
• doi:10.1179/sre.1975.23.176.88
  
• Vincenty, T. Geodetic inverse solution between antipodal points (PDF) (技术报告). DMAAC Geodetic Survey Squadron. 1975b [2011-07-28]. 
• Vincenty, T.; Bowring, B. R. Application of three-dimensional geodesy to adjustments of horizontal networks (PDF) (技术报告). NOAA. 1978. NOS NGS-13. 
• doi:10.1016/j.physd.2011.11.010
  
• Weierstrass, K. T. W. Über die geodätischen Linien auf dem dreiaxigen Ellipsoid [Geodesic lines on a triaxial ellipsoid]. Monatsbericht Königlichen Akademie der Wissenschaft zu Berlin. 1861: 986–997 （German）. PDF.  引文格式1维护：未识别语文类型 (link)

External links

• Online geodesic bibliography, approximately 180 books and articles on geodesics on ellipsoids together with links to online copies.
• Implementations of Vincenty (1975a) for oblate ellipsoids:
  • NGS implementation, includes modifications described in Vincenty (1975b).
  • NGS online tools.
  • Online calculator from Geoscience Australia.
  • Javascript implementations of solutions to direct problem and inverse problem.
• Implementation of Karney (2013) for ellipsoids of revolution in Geographiclib (Karney 2014):
  • GeographicLib web site for downloading library and documentation.
  • GeodSolve(1), man page for a utility for geodesic calculations.
  • An online version of GeodSolve.
  • Planimeter(1), man page for a utility for calculating the area of geodesic polygons.
  • An online version of Planimeter.
  • geod(1), man page for the PROJ.4 utility for geodesic calculations.
  • Javascript utility for direct and inverse problems and area calculations.
  • Drawing geodesics on Google Maps.
  • Matlab implementation of the geodesic routines (used for the figures for geodesics on ellipsoids of revolution in this article).
  • The first description of the geodesic algorithms from (Karney 2009).
• Geodesics on a triaxial ellipsoid:
  • Additional notes about Jacobi's solution.
  • Caustics on an ellipsoid.