New answers tagged

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