# 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 ...
• 2,274

### 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, ...
• 1,972

### 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.
• 8,553

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

### 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,375
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,091

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

### 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 ...
• 611
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,091
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
Accepted

### Selecting most scattered points from a set of points

Here is an approximate solution. Since N is so large and M is so small, how about the following: Compute the convex hull of N Select up to M points from the hull that satisfy your maximum distance ...
• 336
Accepted

### applications of computational geometry in fields such as CFD?

if my years in the industry have taught me anything, it's this: everything depends on the grid. developing a robust solver that efficiently converges to machine zero might be the flashy rock star job,...
• 270

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

### 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 ...
• 8,087
Accepted

### How to determine if a point is outside or inside a curve

There's a simple test to see if a point $(x, y)$ is enclosed within a curve. Draw a ray from $(x, y)$ to infinity, and count how many times it crosses the curve; if the count is odd, then $(x, y)$ is ...
• 8,087

### 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 ...
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,...
• 591
Accepted

### area of voronoi cell

Your question seems to imply that the cells you get extend to infinity. But, since cells are just polyhedra, it is easy to intersect them with your domain which, most of the time, is also just a ...
• 50.2k

### 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 ...
• 2,961
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,286
Accepted

### A method to determine whether a point can be contained within a circle with no neighbouring points

Let the circle centered at your blue point with radius $r$ be denoted as $C_r$ and with radius $2r$ (the solid circle in your diagram) as $C_{2r}$. For each red point $p_i \in C_{2r}$ construct a ...
• 4,567

### Selecting most scattered points from a set of points

With a very large number $N$ of points and a small subset $M$ to be chosen, it may be helpful to consider what is known about continuous versions of the problem in two-dimensions. L. Fejes Tóth ("On ...
• 3,189
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.8k
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
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 ...

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

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