Articles of computational geometry

Showing: point of polytope which maximizes the minimum distance to a vertex is a barycentre?

Let $T_1$ and $T_2$ be two regular $(n-1)$-dimensional simplices with vertices $$(t,0,\ldots,0), (0,t,\ldots, 0),\ldots, (0, 0, \ldots, t),$$ and $$(t-n+1,1,\ldots, 1), (1, t-n+1, \ldots, 1), \ldots, (1,1, \ldots, t-n+1),$$ respectively. Suppose also $m < t < m+1$ for some integer $m$, $0 < m < n$. The intersection of these simplices is a polytope $P$. […]

Prove ( or disprove) that for all kinds of simple polygon, the centroid lies inside the polygon

Is it possible to prove that for all kinds of simple polygon, regardless of whether it is convex or concave and with no opening, the centroid of the polygon must ( or may not) lie inside the polygon? The wiki link above gives example of polygon which has the centroid lying outside the polygon: A […]

Volume of n-dimensional convex hull

I have 2 algorithms for a problem. A solution to the problem is a set of n-dimensional vectors of 0/1’s. A given solution covers any point inside the convex hull of the n-dimensional solution vectors. I want to find out, which algorithm covers a larger area. For instance, assume in the 4d space, algorithm 1 […]

closest pair in N-Dimensional

I have to find the closest pair in n-dimension, and I have problem in the combine steps. I use the divide and conquer.I first choose the median x, and split it into left and right part, and then find the smallest distance in left and right part respectively, dr, dl. And then dm=min(dr,dl); And I […]

Fitting data to a portion of an ellipse or conic section

Is there a straightforward algorithm for fitting data to an ellipse or other conic section? The data generally only approximately fits a portion of the ellipse. I am looking for something that doesn’t involve a complicated iterative search, since this has to run at interactive speeds for data sets on the order of 100s of […]

Maximizing the number of points covered by a circular disk of fixed radius.

Given a set of points in two dimensional space, and a radius r, what is the algorithm to find a disk of radius r that covers the maximum number of points?

Covering all the edges of a hypercube?

Consider an arbitrary $n$- dimensional hypercube: If we select $n – 1$ corners of that hypercube and highlight all $(n – 2)$ dimensional elements that originate from each of the corners is it possible to cover all the $(n – 2)$ dimensional faces of the cube? Also, is it ever possible to cover all the […]

Algorithm to find the point in a convex polygon closest to an external point

Given a convex polygon $P$, and a point $q$ of the plane, external to $P$, what is the fastest algorithm to compute the closest point in $P$ to $q$? A linear algorithm of course works, computing the distance for each vertex of $P$, finding the 2 closest vertices $u$ and $v$ to $q$ and then […]

Correlations between neighboring Voronoi cells

For a sequence $X_1,X_2,X_3,\ldots$ of random variables, what it means to say $X_1$ is correlated with $X_2$ is unambiguous. It may be that the bigger $X_1$ is, the bigger $X_2$ is likely to be. If, as in conventional Kolmogorovian probability theory, we regard all these random variables as functions on a probability space, it makes […]

my plane is not vertical, How to update 3D coordinate of point cloud to lie on a 3D vertical plane

I have a bunch of points lying on a vertical plane. In reality this plane should be exactly vertical. But, when I visualize the point cloud, there is a slight inclination (nearly 2 degrees) from the verticality. At the moment, I can calculate this inclination only. Concerning other errors, I assume there are no shifts […]