The study of computer algorithms which admit geometric descriptions, and geometric problems arising in association with such algorithms. The two major classes of problems are (a) efficient design of algorithms and data classes using geometric concepts and (b) representation and modelling of curves ...

learn more… | top users | synonyms

3
votes
0answers
615 views

Circle Packing Algorithm

I have question related to circle-packing. The problem is to find the circle of minimum radius enclosing four non-overlapping circles of arbitrary radius. I have to write a program in C for this ...
3
votes
0answers
488 views

Detecting Planes through Point Cloud

Having a point cloud say (10000 points) which are randomly dispersed in 3D unit cube, the question is how to find planes within the cube that include more points with an acceptable tolerance (user ...
3
votes
0answers
50 views

Formal proof for detection of intersections for constrained segments [duplicate]

Possible Duplicate: Formal proof for detection of intersections for constrained segments Hi I need to come up with a formal proof for the following statement: Given an arbitrary count of ...
3
votes
0answers
44 views

What are the techniques one can used for rule based plane generation?

I've asked the question here at gamedev SE, but the response wasn't too encouraging. So I try to reask again, from a slightly difference perspective. I have a terrain, which is defined by mesh. And ...
3
votes
0answers
392 views

Distance between a polytope and a point

How to calculate the distance between a convex polytope and a point? Polytope is specified as the solution to the system of linear inequalities. I'm looking for the method that is computationally ...
3
votes
0answers
151 views

The $n$-shortest lattice vectors problem in $\mathcal{R}^2$

I am looking for an algorithm to compute the $n$ shortest lattice vectors in $\mathcal{R}^2$. The problem statement is as follows: Given a lattice $L: \{ m \vec{u}+n\vec{v} \} \in \mathcal{R}^2$, a ...
2
votes
3answers
392 views

What does “identity map $id$” mean?

What does "identity map $id$" mean in this context? Two metrics $d_1$ and $d_2$ on $X$ are said to be Lipschitz equivalent if the identity map $id\colon (X,d_1)\to (X,d_2)$ is bilipschitz.
2
votes
3answers
74 views

Explanation of the following notation

I am having a hard time understanding the meaning of the union operation in this equation. $$C(A)=\bigcup_{x \in A}C(x)$$ For context, here is the sentence: The candidate set for $x$ is $S \cap ...
2
votes
2answers
1k views

Connecting all points on a plane with shortest path possible

I want to connect N nodes, so all are connected, by connecting each node to their closest neighbors. An image of what I'm looking for is below. Currently I solve it like this: I add a random node to ...
2
votes
2answers
198 views

What is inside and outside of complex polygon?

I am reading this paper http://arxiv.org/pdf/1207.3502.pdf Given a complex polygon. Its edges may intersect. The algorithm finds out if given point is inside of polygon or not. It draws a line from ...
2
votes
1answer
1k views

Convex hull has the smallest perimeter

How do you show that the convex hull of a given set of points S, always has the minimum perimeter ? By perimeter i mean the length of the boundary of the hull
2
votes
4answers
2k views

How to test any 2 line segments (3D) are collinear or not?

if we have two line segments in 3D, what would be the way to test whether these two lines are collinear or not? (I fogot to mentioned that my line segments are 3D. So, I edited the original post. ...
2
votes
2answers
6k views

How to multiply vector 3 with 4by4 matrix, more precisely position * transformation matrix

All geometry in computer graphics are transformed by position * transform matrix; The issue is the fact that position is a vector with 3 components (x,y,z); And transform matrix is a 4 by 4 with one ...
2
votes
2answers
160 views

Given four points, verify if they form a Tetrahedron

As per the title, I've been requested to build a program that -given 4 points in space- determine if they form a 3D shape and if this is case to present it's volume. For the volume part of the ...
2
votes
3answers
2k views

Given a tetrahedron, how to find the outward surface normals for each side?

Say I have a triangle in $3$D space. I can get the surface normal by calculating the vector cross product of two of the edges. But, lets say I make this a tetrahedron. How can I work out the outward ...
2
votes
1answer
170 views

Drying blood - an algorithm for calculating the geometry of blood stains

Motivation A bucket full of blood gets spilled over the floor. Question: What shape will the dried blood stains have? Abstraction The blood is modeled by a set of interacting particles (e.g. SPH). ...
2
votes
1answer
512 views

Voronoi average number of vertices $< 6$

My text says "the average number of vertices of the Voronoi cells is less than six". Then it creates the vertex "at infinity", connects the half-infinite edges to this vertex and shows the equation: ...
2
votes
2answers
927 views

Finding the/a point within an irregular polygon which is furthest from polygon's line segments?

I'd like to determine which point(s) within an irregular polygon are furthest from the edges. Is there an existing algorithm to determine this? Also, if it's already out there, I'd like to do a ...
2
votes
2answers
163 views

Convex hull for convex polygons

Is there something tricky about that? Or I should use some of the standard convex hull algorithms ? I mean, I don't see anything different between creating convex hull for a set of points and creating ...
2
votes
1answer
121 views

Collinear points in 3dimension

Given three $3D$ points: $A,B$ and $C$, what is the procedure to check if they are collinear? In general, given $n$ points in $m$-dimension, how should one find out, if these $n$-points defines a ...
2
votes
2answers
422 views

Flood algorithm - find polygon containing a given point.

I have some code that represents a set of a set of interconnected line segments in 2D, in pseudo-code it'd be like this: ...
2
votes
2answers
1k views

Determing the distance from a line segment to a point in 3-space

Imagine I have a line segment defined by endpoints $p_1$ and $p_2$, and some 3-space coordinate $q$. Is there a robust (in the sense of never giving divide-by-zero errors) way to quickly determine ...
2
votes
1answer
103 views

What is the mathematical relationship between the number of faces in a mesh and its vertices?

An "open and planar quad mesh" (more description below) with 4 mesh faces has 9 vertices, the same mesh with 8 faces has 15 vertices (2 faces at every X-axis row, 4 faces at every Y-axis ...
2
votes
1answer
241 views

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. ...
2
votes
1answer
111 views

Equality of Voronoi diagram

What can we say about two sets $A$ and $B$ if both of them have the same Voronoi diagram. First, I thought if the Voronoi diagram are equal so the sets also should be equal, but by definition, ...
2
votes
1answer
195 views

How do I calculate the unique k-dimensional hypersphere's center from k+1 points?

I'm working with the Bowyer-Watson algorithm to determine the Delaunay tessellation of stochastic points in k-dimensional space. This algorithm assumes that the center of a simplex can be used as the ...
2
votes
1answer
110 views

Computing the point which is closest to many Planar surfaces

Suppose, i have been given different planes which orients to different direction (i.e. i know only the plane parameter of those planes). If i am able to find out planes (probably more than 3 planes) ...
2
votes
2answers
1k views

Point closest to a set four of lines in 3D

Given 4 lines in 3D (represented as a couple of points), I want to find the point in space which minimizes the sum of distances between this point and every line. I'm trying to find a way to ...
2
votes
1answer
232 views

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? ...
2
votes
1answer
93 views

Minkowski sum of two polytopes via the halfspace representation

If i have two polytopes denoted by $P_1, P_2 \subset \mathbb{R}^d$, suppose their halfspace representations are respectively $H_1x \leq K_1$ and $H_2x \leq K_2$. Now, considering their Minkowski sum, ...
2
votes
1answer
53 views

Good data structure for hyperbolic tiling

Say you're doing something computational where each data point is a tile in a (not necessarily Euclidean) 2-dimensional tiling, for instance, a Life-like cellular automata. You might want a data ...
2
votes
1answer
51 views

What's wrong with this pseudocode for Forster-Overfelt's version of the Greiner-Horman polygon clipping algorithm?

The Problem I'm trying to understand and implement the Forster-Overfelt version of the Greiner-Horman polygon clipping algorithm. I've read the other Stackoverflow post about clarifying this ...
2
votes
1answer
414 views

Distance between point and plane & orthogonal projection matrix

I am poor in mathematics and want to learn few fundamental ethics to understand some of advanced things; For plane $i$, denote $n_i\in\mathbb{R}^3$ and $o_i\in\mathbb{R}^3$ respectively as its normal ...
2
votes
1answer
481 views

Circle Packing: Unsolved Problem in Geometry?

Graham and Sloane minimize the second moment of the centres of a number discs in order to maximize their compactness. They use computational geometry techniques to find the optimal packings for ...
2
votes
1answer
315 views

Obtaining Least square adjusted single line by intersecting many 3D planes

I am working with many 3D planes and looking for a Least square solution for below case. IF I am having many number of 3D planes knowing only one point and the normal vector (for eg. O1 and N1), ...
2
votes
2answers
2k views

Proof that the Convex Hull of a finite set S is equal to all convex combinations of S

In $C^n$, how would you prove that the convex hull of a finite set $S$(convex hull being the intersection of all convex sets which contain $S$) is equal to the set consisting of all convex ...
2
votes
1answer
934 views

How many rectangles can fit in a polygon with n-sides?

I am trying to write an algorithm to solve a problem I have. I have a few ideas of what the algorithm might be like but I am posting to see if anyone else has a better more efficient solution or any ...
2
votes
1answer
153 views

Test if a given point q is a kernel of polygon P

Point $q$ is a kernel of a polygon $P$ if from $q$ we can see all vertices of $P$. In addition, kernel is a intersection of $N$ half planes formed by edges of polygon. Proofs of the above ...
2
votes
1answer
738 views

How to fit largest circle within Voronoi cells?

I have a list of Voronoi cells and would like to place the largest circle possible within each cell. What is the best way to do that? Many thanks, Arthur
2
votes
1answer
1k views

Solid body rotation around 2-axes

I am trying to understand how to describe the rotation of a solid body flying in 3D space. From physics forums, I understand that the rotation of any solid object in space, is around 2 axes ...
2
votes
3answers
119 views

Formal proof for detection of intersections for constrained segments

They told me it was off-topic at stackoverflow. So I am trying my luck here. Yes, it's a homework, but I'm looking for some guidance (or related literature) instead of complete solutions. Please see ...
2
votes
1answer
166 views

Isosceles triangles in a regular n-gon

I'm asked to find whether a certain partition exists. The set which I am partitioning is the set of vertices of a regular n-gon. There are to be two sets in the partition and no three vertices in ...
2
votes
2answers
340 views

Uniform thickness border around skewed ellipse?

I have an ellipse with a given major and minor 'radius'. I then apply a 2D skew affine transformation to it. Then, I want to draw a uniform border inside this new shape, as if a circle were rolled ...
2
votes
1answer
76 views

points in general position

I'm really confused by definition of general position at wikipedia. I understand that the set of points/vectors in R^d is in general position iff every (d+1) points are not in any possible hyperplane ...
2
votes
1answer
54 views

What does $E^d$ mean?

I was reading the paper "Cutting Hyperplanes for Divide-and-Conquer" by B. Chazelle and in the introduction I came across the following: "Let $H$ be a set of $n$ hyperplanes in $E^d$." What does $E^d$ ...
2
votes
1answer
84 views

how many unit balls are needed to cover a unit sphere (1-dense set on a unit sphere)

There is an exercise in a geometry textbook to prove that "any $1$-dense set in the unit sphere $S^{n-1}$ has at least $\frac{1}{2}e^{n/8}$ points". It is supposed to be easy. A set $T$ is ...
2
votes
1answer
66 views

Reference for important results in linkage theory and their proofs

Are there books or lecture notes that comprehensively introduce the (geometric/topological) theory of mechanical linkages, as well as important results and their proofs? For instance, Kempe's ...
2
votes
1answer
116 views

How to extract the indeterminates from a set of polynomial?

I am a biologist and I am facing a huge problem. I would like to extract the indeterminates of a set of polynomials, for example, I have: $f_{1} = \{\\x_{3}^{2} + x_{1}*x_{2} + x_{1} + x_{1}*x_{3},\\ ...
2
votes
1answer
544 views

Angle between different rays (3d line segments) and computing their angular relationships

I have several positions (say A,B,C,..) and I know their coordinates (3d). From each point, if a certain ray is passing in a way to converge them at a given (known) point (say O). This point O ...
2
votes
1answer
125 views

incident angles between rays, falling on an oblique plane

I am having really two simple questions, but following two things are confusing me. Question 1 If I know plane parameter (v3) of a given plane (say AB); if a pair of rays are incident at a ...