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
356 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
137 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
346 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
165 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
913 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
5k 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
120 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
161 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
461 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
837 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
161 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
69 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
370 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
656 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
100 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
213 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
101 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
173 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
109 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
221 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
328 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
425 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
291 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
883 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
141 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
674 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
113 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
158 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
325 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
17 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
35 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
53 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
76 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
58 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
113 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
485 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
118 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 ...
2
votes
2answers
109 views

Books for Geometry processing

Please suggest some basic books on geometry processing. I want to learn this subject for learning algorithms in 3d mesh generation and graphics. Please suggest me subjects or areas of mathematics i ...
2
votes
1answer
82 views

Computational geometry

Computational geometry? (Computational geometry) Given a set of n randomly scattered points for even n = 2,4,6,...,50 . Find the maximum number of lines between the pairs of nodes in such a way the ...
2
votes
1answer
38 views

Fragemented linear feature alignment technique

I am having set of linear features lie on a plane (it does not a matter whether the pane is vertical or horizontal). all linear features are either parallel or othogonal to the vertical axis or ...
2
votes
1answer
45 views

How to estimate orientation errors of an image with respect to known data (line features)

I think this is very simple but for me, it is confusing to figure out a way. Here is my problem. I have been given a 3d line segment list obtained from a field survey. So I know each end point ...
2
votes
2answers
233 views

Given two sets of vectors, how do I find a change of basis that will convert one set to another?

Given two sets of dimension $n$ vectors $\lbrace v_1 , v_2 , \ldots , v_m \rbrace$, $\lbrace u_1, u_2, \ldots , u_m \rbrace$, where $m > n$, is there a computational method (in particular, using ...
2
votes
1answer
450 views

Finding points on ellipse

I have ellipse in 2D. I want to compute fixed number of points on this ellipse with constant angular seperation between those points. My first idea was to generate line equations from center of the ...