# Tag Info

### 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,187

### 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,242

### 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.
• 11.8k

### 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-...
• 391

### 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,485
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,981

### 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,702

### 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,582
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,315
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,239
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