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

2
votes
2answers
335 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
4answers
3k 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
9k 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
1answer
29 views

Determine the locus

Let $0<a<b$. Consider two circles with radii $a$ and $b$ and centres $(a, 0)$ and $(b,0)$ respectively with $0<a<b$. Let $c$ be the center of any circle in the crescent shaped region $M$ ...
2
votes
2answers
42 views

Proof of correctness of a formula for the area of a polygon

Let $P$ be a $n$-gon with vertices $(x_1,y_1),\ldots,(x_n,y_n)$ enumerated clockwise. Then the area $\text{Area}(P)$ of $P$ is $$ \text{Area}(P) = \sum_{i=1}^n\frac{1}{2}(x_{i+1}-x_i)(y_{i+1}+y_i).$$ ...
2
votes
1answer
183 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
769 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
1k 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
351 views

Find polygon with smallest perimeter that encompasses all points

Given a random set of points in 2D space such as: How would one go about finding the smallest perimeter polygon that encompasses all points and has a point as each one of its vertices? For the ...
2
votes
1answer
173 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
254 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
718 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
991 views

Finding the tangents common to two rotated ellipses?

Is there a way to find the four tangents that two rotated ellipses share? I believe that if two ellipses do not intersect and do not contain one another, they will have four tangents in common and I ...
2
votes
2answers
106 views

Approximating Euclidean geometry, restricted to $\mathbb{Q}$

I'm having trouble putting this into a fully coherent question, so I'll give the broad question, then a few bullet points to give you a better idea of what I'm asking. I'm looking for a line of ...
2
votes
2answers
2k 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
113 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 column)...etc....
2
votes
1answer
338 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
128 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
241 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
114 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
1answer
315 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
57 views

Largest enclosed (inscribed) circle in cloud of points

I have a set of points that approximately lie on a circle. I would like to compute the largest circle that does not contain any of the points. Of course, one could draw the circle far away from the ...
2
votes
1answer
78 views

Area of Convex hull

For every point set $A \subset R^2$, prove that in general the sum of the coordinates of $\phi(T)$ is independent of a triangulation T and is associated to the area of the Convexv_Hull(A). We define ...
2
votes
1answer
47 views

Fastest computation to find out if two vectors intersect (programming problem)

I'm trying to write a program that should solve a 12x12 rush hour problem: I won't go in the details of this program to much. The program already works for 6x6 puzzles, but for 12x12 puzzles, it is ...
2
votes
1answer
75 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
236 views

On finding the nondominated set of vectors. How to understand this algorithm?

L et us denote by $x_i(v)$ the $i$th coordinate of $v \in \mathbb{R}^d$. Then $v = \left [ x_1(v), x_2(v), \dots ,x_d(v) \right ]$ We say that a $v \in \mathbb{R}^d$ dominates another vector $w \in ...
2
votes
1answer
575 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
606 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 non-...
2
votes
1answer
358 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
1answer
280 views

Algorithm for computing the plane that passes through three arbitrary points

I'm writing a computer graphics library, and I'd like to compute the plane that passes through three arbitrary points, $p$, $q$ and $r$. I'm defining the plane in the form of $Ax + By + Cz + D = 0$. ...
2
votes
1answer
1k 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
3answers
132 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
188 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
402 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
129 views

Does a convex hull solution in 3 dimensions result in a minimum-area or maximum-volume solution?

The wikipedia entry for convex hull shows a 2-d example of a random set of points on x-y plane, and the "elastic band" solution that bounds the points with the convex hull solution. The definition of ...
2
votes
2answers
83 views

Reliable test for intersection of two Bezier curves

Is there a test which reliably decides whether two Bezier curves intersect or not? I don't need to know how many intersections there are or at what parameters they appear at. I just would like to ...
2
votes
1answer
61 views

Bisecting points on a circle

I was working on the following problem. Given n points on a circle, where a point can be specified by its angle from the vertical, how does one find a diameter of the circle such that the number of ...
2
votes
2answers
62 views

Test if point is in convex hull of $n$ points

I have $n$ points $x_1,\dots,x_n\in\Bbb R^d$, and I would like to check that some other point $y$ lies in their convex hull. How can I do this in some efficient way? I think that there was an ...
2
votes
1answer
75 views

segment intersecting a tetrahedron

I am trying to write C++ code to find the intersection points of a segment intersecting a tetrahedron. I reduced the problem like this: For each face of the tetrahedron (a triangle), find the ...
2
votes
1answer
65 views

sample variance of regular polygon upon superimposition of vertices

Given, the vertices of a regular polygon, the centroid here would be the sample mean of the vertices and we assume it to be at the origin. The distance from each vertex to centroid is $\frac{s}{2\sin(\...
2
votes
2answers
845 views

How can I define a measure of similarity between two line segments in $\mathbb{R}^2$?

I have two segments in $\mathbb{R}^2$ and I would like to define a measure of similarity between the two segments. My idea is that I can apply: a scale transformation $s$ in order to equate the ...
2
votes
1answer
56 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
98 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 $\epsilon$-...
2
votes
2answers
48 views

Room for computational geometry in advanced algorithms course

I am currently putting together an independent study in advanced algorithms and because of my interest in (computational) geometry, wanted to include as many interesting algorithms from this field as ...
2
votes
2answers
141 views

Polytope parametrization

How one could parametrize a convex polytope? By parametrization I mean something like in multiple integrals, when to integrate over an area one can integrate over one variable in an interval $[l,r]$ ...
2
votes
1answer
88 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
124 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
2k views

How to find whether the line is inside the polygon or outside.

I have a polygon How can i prove whether the black color line lies outside the polygon or inside the polygon . Given the coordinates of the black line and all the vertices of the polygon.
2
votes
1answer
798 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 is ...
2
votes
1answer
144 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 ...