# Tag Info

42

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 dynamics of two interacting particles which, for example, interact by gravitational or Coulomb forces. The solution to this problem can often be found in closed form ...

33

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, then no matter the starting point, with probability one (a.k.a. almost surely), the random walk will eventually get to a specific designated point ("Rome"). ...

29

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.

25

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-offs between various reasonable-sounding conditions. (Arrow's impossibility theorem).

24

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 of a million-dollar Clay Millenium Prize. But the two-dimensional version has already been resolved a long time ago, with an affirmative answer. Terry Tao notes ...

21

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 "Smallest Enclosing Ellipses -- An Exact and Generic Implementation in C++". The paper's 150 pages long, but, fortunately for us, the venerable CGAL ...

14

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 simultaneous reduction of three matrices to a canonical form (weaker condition compared to the above) is required: $$Q^T A_1 Z = \tilde{A_1},\quad Q^T A_2 Z = \... 13 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 & \cdots & a_d \end{array}\right), where it is not so important how you obtain the columns a_2, \ldots, a_d of A, as long as \{v, a_2, \ldots, ... 12 I would say that there are a number of reasons why there are no computational science contests besides the potentially massive computational resources required. Time limits: Writing scientific computing code is usually not something that you want to rush. A lot of emphasis is on making sure it is correct, and thorough consideration of test/corner cases. ... 12 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 in the tangent bundle of S^{n-1} at v. This is a map S^{n-1}\to \mathrm{F}S^{n-1} from the sphere to its frame bundle, also known as a global section of ... 11 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 criteria. If Step 2 leaves you with fewer than M points then select 1 point from the interior that maximizes its distance from the previously selected points. ... 10 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, but the unsung heroes are the developers that improve our gridding algorithms. if you're looking for a really great way to lose the effects of a vortex, try ... 10 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 systems) is relatively easy whereas entanglement among three or more systems is an unsolved mess with probably a hundred papers written on the topic. The root of ... 10 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 that you can shrink the size of the ellipse slightly along the vector (1, 1)^\top / \sqrt{2} (or thereabouts). Another formulation that you could try is to ... 8 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 inside the enclosed region; otherwise, it's outside. To turn this into a practical algorithm, you could first build polygonal approximation of the curve and ... 8 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 Morton key to search only in a small number (\mathcal{O}(1)) of nearby boxes, bounded by your distance criterion. The search for each box is \mathcal{O}(\log ... 8 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, all of them lie on a given smooth surface. Furthermore, you know the unit normal {n} everywhere on the surface. Then you know the unit normal to the surface ... 7 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 polyhedron. If your domain is finite, then so are all the cells. In other words, if you encounter a cell with a vertex at infinity, then you need to determine the ... 7 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 applying the finite element matrix using small reference matrices and geometry-specific transformations. For implicit problems, this is usually done in ... 7 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-is. You also might be able to modify the algorithm to callback to f directly. There's a popular implementation at http://paulbourke.net/geometry/polygonise/ ... 6 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 circle of radius r centered at p_i and call it C_i. Any circle centered inside of C_i contains p_i and is therefore invalid. Any circle centered inside ... 6 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 the sum of distances determined by a pointset", Acta Math. Acad. Sci. Hungar., 7:397–401, 1956) showed that the set of M points on a circle which maximizes ... 6 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 the usual method, but I haven't seen one in practice. One question I have for you is what are you doing that requires lots of checks for which element a point ... 6 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 collision detection algorithms, you search systematically for a separating axis between the cylinders. For future reference on similar problems, the authors of Real-... 6 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 the Gauss elimination method, for example, then you need to pre-compute all elements of A and keep them during the algorithm. If you were to use Krylov-type ... 6 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 that the obtained shape is smoother). Subdivision To grasp the intuition, imagine you want to "smoothen" a 2D square. The 2D square is not smooth because it has ... 6 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 you know how to define the three basis functions on this triangle. They are: \hat N_1(\xi,\eta) = 1-\xi-\eta,\\ \hat N_2(\xi,\eta) = \xi,\\ \hat N_3(\xi,\eta)...

6

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 to this problem, and published the following manuscripts: T. Birdal, B. Busam, N. Navab, S. Ilic and P. Sturm. "A Minimalist Approach to Type-Agnostic ...

Only top voted, non community-wiki answers of a minimum length are eligible