43
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,042
37
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,192
31
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.
- 10.7k
28
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-...
- 381
27
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,455
22
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 &...
- 3,891
16
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,592
13
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 ...
- 791
13
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, "...
- 3,891
12
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.4k
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 ...
- 9,813
8
votes
Matrix free finite elements method for visualization in process tomography
To add to Dmitry's answer (copied over from the deleted version of this question):
Matrix-free finite elements are relatively well-known. For explicit methods for transient problems, this involves ...
- 3,102
8
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,...
- 611
8
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 ...
- 583
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
Accepted
Matrix free finite elements method for visualization in process tomography
Matrix-free method is a general name for a class of algorithms, rather than a particular method.
For example, consider solving the linear equation $Ax=b.$ If you were to solve this this problem using ...
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 ...
- 981
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-...
- 4,794
7
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,042
6
votes
Accepted
Point inside curved finite element
I don't think you can do better in general than mapping to the reference element and testing there. If your mapping is somehow special, you might be able to develop a test that's more efficient than ...
- 10.9k
6
votes
Accepted
How to determine whether two cylinders intersect or not?
David Eberly has a good description of the solution (with pseudocode) here: http://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf
The short summary: like most convex-convex ...
- 331
6
votes
How to "smoothen" (not just refine) a 2D/3D polygonal mesh
To complement the two answers from Daniel Shapero and Nicoguaro:
Basically, there are two ways of smoothing a mesh, subdivision (generate new vertices) and smoothing (move the points in such a way ...
- 2,305
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 ...
- 53.7k
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,219
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
Rank constrained SDP
The constraint $\mbox{rank}(X) <= d$ is in general a non-convex constraint. Sorry.
A commonly used approach is to minimize the Schatten 1-norm of X (the sum of singular values of X) as a ...
- 18.5k
5
votes
Point inside curved finite element
If your element is quadratic, you can find an implicit equation of the three quadratic edges of the triangle in function of $x,y$, in the form $E_1(x,y)=0$, $E_2(x,y)=0$, $E_3(x,y)=0$ (more ...
- 2,305
5
votes
How to "smoothen" (not just refine) a 2D/3D polygonal mesh
As mentioned in the answer by @DanielShapero, you can follow an approach based on local approximations of the curvature for your nodes. In the post he suggest, there is an article by Desbrun. I would ...
- 8,312
Only top scored, non community-wiki answers of a minimum length are eligible