New answers tagged computational-geometry
0
The following procedure achieves your requirements:
Step 1: Find the smallest circle that encloses all points. (There are standard algorithms for this.)
Step 2: Compute the area of that circle.
Step 3: Compute the scaling ratio $c$ needed to achieve the desired area. (For instance if the area of that circle is 100 and you want area 5, then your scaling ...
1
I would suggest you try using RANSAC. Randomly pick a triplet of $a$ points and $b$ points, find an affine transformation that maps the former to the latter, find all other points that it maps well, and create that as a candidate cluster those. Repeat many times, and keep the best cluster. Remove the points in that cluster, and then repeat.
This might ...
3
It is common to prove the decidability of first-order Euclidean geometry by encoding the language of Euclidean geometry into the language of real closed fields and then showing that the latter is decidable. A singly-exponential space upper bound on deciding the first-order theory of real closed fields was proven in Ben-Or, Kozen, and Reif (1986). This ...
1
If you are using Python, you can use the implementation of sklearn pairwise_distances_argmin_min that given two point sets A and B returns the closest point pB in B and the distance from pA to pB for each point pA in A.
You then select the pair of points with the smallest distance of all in $O(n\log n)$:
from sklearn.metrics import ...
1
I propose the following approach.
Decompose each polyhedron into a union of convex polyhedra, say $A = A_1 \cup \cdots \cup A_m$ and $B = B_1 \cup \cdots \cup B_n$.
Convert each convex polyhedron from V-representation (its list of vertices) to H-representation (intersection of half-spaces, given by linear inequalities).
Compute the intersection as $A \cap B ...
0
It seems you are trying to perform onion peeling(convex layers) from the inside out, which is not possible.
A convex hull of given points is a polygon that contains all given points either on itself or inside it.
To solve the problem you have described you must generate a convex hull using an algorithm of choice. Now that you have the outer layer, for the ...
2
Most spatial indexes should be good, especially if your rectangles are axis aligned.
Spatial indexes typically have about $O(log{M})$ insertion time so you could build in index in $O(M * log{M})$.
Lookup time is similar, so finding the best/correct rectangle for every point should be around $O(N * log{M})$.
For rectangles, the simplest index is probably a ...
Top 50 recent answers are included
