44
votes
Good examples of "two is easy, three is hard" in computational sciences
One example that appears in many areas of physics, and in particular classical mechanics and quantum physics, is the two-body problem. The two-body problem here means the task of calculating the ...
- 3,237
38
votes
Good examples of "two is easy, three is hard" in computational sciences
In one and two dimensions, all roads lead to Rome, but not in three dimensions.
Specifically, given a random walk (equally likely to move in any direction) on the integers in one or two dimensions, ...
- 2,272
33
votes
Good examples of "two is easy, three is hard" in computational sciences
A famous example is the boolean satisfiability problem (SAT). 2-SAT is not complicated to solve in polynomial time, but 3-SAT is NP-complete.
- 12.6k
31
votes
Good examples of "two is easy, three is hard" in computational sciences
In social choice theory, designing an election scheme with two candidates is easy (majority rules), but designing an election scheme with three or more candidates necessarily involves making trade-...
- 411
28
votes
Good examples of "two is easy, three is hard" in computational sciences
Here's one close to the hearts of the contributors at SciComp.SE:
The Navier–Stokes existence and smoothness problem
The three-dimensional version is of course a famous open problem and the subject ...
- 2,505
23
votes
Accepted
How do I find the minimum-area ellipse that encloses a set of points?
Theory
The 1997 paper "Smallest Enclosing Ellipses -- Fast and Exact" by Gärtner and Schönherr addresses this question. The same authors provide a C++ implementation in their 1998 paper &...
- 4,021
17
votes
Good examples of "two is easy, three is hard" in computational sciences
Simultaneous diagonalization of two matrices $A_1$ and $A_2$:
$$
U_1^T A_1 V = \Sigma_1,\quad U_2^TA_2V=\Sigma_2
$$
is covered by existing generalized singular value decomposition.
However, when the ...
- 8,742
14
votes
Generate a set of orthogonal vectors to a given vector
In order to find such a set of vectors, you can use the Householder QR factorization. Let your unit vector $v$ be given. Define a nonsingular matrix $A$ by
$$
A = \left(\begin{array}{cccc} v & a_2 ...
- 831
14
votes
Accepted
Generate a set of orthogonal vectors to a given vector
There is a known mathematical question here: you are given a unit
vector, lying on the $(n-1)$-sphere in $\mathbb{R}^n$, $v\in S^{n-1}$, and you would
like to associate with each such vector a frame ...
- 11.5k
14
votes
Accepted
How to find the smallest ellipse covering a given fraction of a set of points?
You asked for the smallest ellipse. An ellipse so small that its smallestness needs to be italicized. Others have provided answers that identify smallish ellipses, but, as Miracle Max says, "...
- 4,021
10
votes
Good examples of "two is easy, three is hard" in computational sciences
There are plenty of examples in quantum computing, although I've been out of this for a while and so don't remember many. One major one is that bipartite entanglement (entanglement between two ...
- 209
10
votes
How do I find the minimum-area ellipse that encloses a set of points?
With your formulation of the constraints, you can only produce ellipses where the semi-major and semi-minor axes are aligned with the coordinate axes, but it's clear from the figure that you attached ...
- 10.5k
9
votes
Accepted
How to calculate the geodesic curvature of a discrete 3D curve?
Why don't you try something geometric rather than numerical. I propose the following approach.
Let the points from the loop form the sequence $\alpha_i \,\, : \,\, i = 1, 2, 3 ... I$ and as you said,...
- 621
9
votes
Good examples of "two is easy, three is hard" in computational sciences
A smooth curve of degree 2 (i.e. given as the solution of $f(x,y) = 0$ where $f$ is a polynomial of degree 2) with a given point is rational, meaning that it can be parameterized by quotients of ...
- 613
8
votes
Good examples of "two is easy, three is hard" in computational sciences
Angle bisection with straightedge and compass is simple, angle trisection is in general impossible.
- 3,237
8
votes
Good examples of "two is easy, three is hard" in computational sciences
Here's a neat one from optimization: the Alternating Direction Method of Multipliers (ADMM) algorithm.
Given an uncoupled and convex objective function of two variables (the variables themselves ...
7
votes
Efficiently finding all (x,y,z) points within certain distance of point P
You can use Morton keying to sort the coordinate locations by binning them into cubes of some specified size $d$. This is an $\mathcal{O}(N\log N)$ operation. Then, given any point P, you can use its ...
- 1,031
7
votes
Accepted
3D contour mesh computation
I think you could use the "marching cubes" algorithm. If memory serves, it requires a grid of samples as input, so at the very least you should be able to sample your function and run the algorithm as-...
- 5,076
6
votes
Accepted
Fitting Implicit Surfaces to Oriented Point Sets
I was surprised for not receiving a satisfactory answer to the question above and my investigations showed me that this, indeed is an unexplored area. Hence, I put some effort in developing solutions ...
- 2,339
6
votes
Finding Shape Functions for a Triangle in 3D coordinate space
This is actually quite simple. Let's say you have your (two-dimensional) reference triangle $\hat K=\left\{(\xi,\eta)\in {\mathbb R}^2: 0\le \xi \le 1, 0\le \eta\le 1, \xi \le (1-\eta)\right\}$. Then ...
- 56.8k
6
votes
Good examples of "two is easy, three is hard" in computational sciences
The problem on which I originally made that comment is a linear algebra problem: consider the linear matrix equation
$$
\sum_{i=1}^k A_i X B_i = C,
$$
where $A_i,B_i,C \in \mathbb{R}^{n\times n}$ are ...
- 12.6k
6
votes
Accepted
Selecting most points from a set of points with distance constraint
This can be stated as a formal optimization problem:
$$ \begin{aligned}
\max& \sum_i \color{darkred}x_i \\
& \mathit{\color{darkblue}{dist}}_{i,j} \ge \mathit{\color{darkblue}{...
- 271
5
votes
Accepted
Algorithms to extract trajectory lines out of 3D point clouds
I will summarize a couple of possibilities:
As a baseline, I would begin with a Hough transform kind of approach:
Iterative Hough Transform for Line Detection in 3D Point Clouds
Christoph Dalitz,...
- 2,339
5
votes
Accepted
Optimally "morph" one set of points into another
You may consider numerical optimal transport.
It does not exactly fit your specification, but for your image morphing application it may be well suited.
In the discrete setting, given your two set of ...
- 2,345
5
votes
Accepted
Find connected circles
You don't need to check each pair of circles, so you can apply one of the neighour search algorithms. They restrict the distance calculations to the circles in the vicinity of each other by generating ...
- 430
5
votes
3D contour mesh computation
In addition to the voxel-based approach that rchilton suggests, you could also look at Delaunay-type algorithms. For example, the Computational Geometry Algorithms Library (CGAL) has some built-in ...
- 10.5k
5
votes
Accepted
Efficient root finding algorithm for monotonic function
It seems your main concern is bracketing the root in as few iterations as possible, since each iteration is costly. In some cases you have found the regula falsi method to be unreliable, suggesting ...
5
votes
How can one prove the duality of Voronoi and Delaunay?
The duality between Voronoi cells and vertices of the triangulation is pretty clear: each vertex of the Delaunay triangulation is a site in the Voronoi diagram which gets associated with its Voronoi ...
- 241
5
votes
Good examples of "two is easy, three is hard" in computational sciences
Type inference for Rank-n types. Type inference for Rank-2 is not especially difficult, but type inference for Rank-3 or above is undecidable.
Only top scored, non community-wiki answers of a minimum length are eligible