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
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
1answer
928 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
2answers
32 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
0answers
48 views

packing problem of semicircles into rectangle

I have problem. How can I get the maximum amount of semicircles (for example radius $35\;mm$) into rectangle $(485\times 185\:mm)$. I found many articles about packing of circles but nothing about ...
2
votes
0answers
49 views

Intersecting convex figures

Take in the real plane a finitely long horizontal line segment and connect the two endpoints by a convex path, above the segment, with the property that the only extreme points of the convex hull of ...
93
votes
21answers
38k views

How to check if a point is inside a rectangle?

There is a point $(x,y)$, and a rectangle $a(x_1,y_1),b(x_2,y_2),c(x_3,y_3),d(x_4,y_4)$, how can one check if the point inside the rectangle?
1
vote
1answer
47 views

Total number of lines in a 2D grid

I have a 2D grid of $M \times N$ points. I need to find the total number of lines (not line segments) passing through these points including the diagonals. For example: $M=2,N=2$: Number of lines $= ...
0
votes
0answers
17 views

Extension of Isovist concept for a point - to Isovist for a polygon

There is the concept of Isovist/Visibility polygon. They both talking about volume of space visible from a given point in space. My question: What is the algorithamic solution of this problem for a ...
1
vote
1answer
23 views

What is an offset bisector in 2D polygon skeletonization?

I'll be referring to the definition of the offset bisector from the definitions section of CGAL's 2D Straight Skeleton and Polygon Offsetting module. The halfplane to the bounded side of the line ...
0
votes
0answers
9 views

Integrate gaussian over general simplex

I need to compute the volume of an $n$-dimensional simplex where some dimensions are distributed uniformly and some normally. Can this be approximated well in polynomial time?
-1
votes
1answer
44 views

How can I find an algebraic formula to test whether two line segments intersect or not?

Suppose, $AB$ and $CD$ are two line segments. And, they have slopes $m_1$ and $m_2$ respectively. They will intersect with each other if, $m_1 \ne m_2 .$ Suppose, $A(x1, y1); B(x2, y2); C(x3, y3); ...
1
vote
1answer
37 views

How many techniques are there to test collinearity of $n$ points?

How many techniques are there to test coliniariry of n points? For example, suppose we have 4 points A, B , C, D. How many ways can it be tested that they are collinear? This answer lists 03 ...
1
vote
1answer
26 views

What is the name for the image form you get you take a line segment and sweep it through a region of space?

For instance, if you were to take a line segment and translate it along a coplanar path, then you'd get a plane. If the path is cyclic and on that path you rotate the line segment on the axis ...
1
vote
1answer
52 views

Determining the position of a polygon inside a circle from only the angle of opposing sides/edges.

For illustration click here I have a simple convex irregular polygon (octagon in example image) inside a circle (circle and polygon are not always concentric and never touching or intersecting) and I ...
2
votes
1answer
61 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 ...
0
votes
1answer
44 views

differentiating an integral with respect to a variable which also affects the region of integration

I am considering taking the derivative of the function $$F(\mathbb{x_1},\mathbb{x_2},\mathbb{x_3}) = \displaystyle \int_{V_1} ||x-\mathbb{x_1}||\phi(x)\,dx + \int_{V_2} ||x-\mathbb{x_2}||\phi(x)\,dx ...
3
votes
0answers
38 views

'Unrolling' the neighbourhood of a space curve

I have a space curve $\gamma : \mathbb{R} \longrightarrow \mathbb{R}^3$, sampled at $n$ discrete points. I have implemented an algorithm that gives me an approximation to $\gamma$'s tangent, normal ...
3
votes
2answers
63 views

Box-Counting Dimension with finite resolution

Does the method of determining dimension of a shape via the Box-Counting dimension (Minkowski–Bouligand dimension) have to be performed on fractals (objects that look the same at all scales), or can ...
1
vote
0answers
16 views

Epipolar geometry - Fundamental matrix derivation (Hartley, Zisserman)

I have a question to the following derivation of the fundamental matrix by Hartley and Zisserman in "Multiple View Geometry in computer vision" (Link, page 5): Why is it possible to do the very ...
5
votes
0answers
48 views

Reconstruct polyhedron from sections

There is a convex polyhedron $P \subset \mathbb{R}^{3}$ and there are its planar sections $S_{1}, \ldots, S_{n}$ througth planes $\pi_{1}, \ldots, \pi_{n}$, $S_{i} \subset \pi_{i}$. All these $S_{i}$ ...
0
votes
1answer
34 views

equation of a cylinder jacket

how would you calculate this? A circular cylinder, height $14$, base radius $2$, has the axis of rotation! What is the equation of the cylinder jacket when the center of the base circle is the ...
6
votes
0answers
115 views

Balanced, center-free set. [closed]

We say that a finite set $\mathcal{S}$ of points in the plane is balanced if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC=BC$. We say ...
0
votes
3answers
40 views

Obtaining the four corner coordinates of a square from the center point.

I'm trying to get the corner coordinates of a Square (NOTE, always a square) problematically. (EX: With a formula) and I'm having a hard time adding this into my computer application. Here's an ...
2
votes
0answers
21 views

Sum of distances of points in unit closed disk

Let $D$ be the closed unit disk in the plane, and let $p_1, p_2, \dots, p_n$ be fixed points in $D$. My question is, does there necessarily exist a point $p$ in $D$ such that the sum of the distances ...
0
votes
0answers
39 views

Relation between farthest pair of points and closest pair of points in plane

I am writing program for obtaining distance between shortest and farthest pair of points among the given points in plane .I am able to calculate them both the shortest one using divide and conquer ...
2
votes
0answers
54 views

3D kinematic geometry problem motivated by chemistry

It is well known that six carbon atoms can form a ring called cyclohexane. Since the angle between bonds is $\cos^{-1}\left(\frac{-1}{3}\right)\approx 109^\circ$, the ring is not a planar hexagon. ...
2
votes
2answers
8k views

How to find the third coordinate of a right triangle given 2 coordinates and lengths of each side

p2 |\ |b\ | \ A| \C | \ |c___a\ p1 B p3 If given point p1 & p2, side A & B how would you find point p3? I know given this information you ...
1
vote
2answers
2k views

Two plane intersection and angle between 2 planes

I am trying to implement my problems in different ways. So, may be though this question has some relation to some other questions, please answer me. We know; Intersection of two planes will be given ...
4
votes
2answers
2k views

How to calculate volume of 3d convex hull?

Convex hull is defined by a set of planes (point on plane, plane normal). I also know the plane intersections points which form polygons on each face. How to calculate volume of convex hull?
3
votes
0answers
49 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
2answers
1k views

Point closest to a set four of lines in 3D

Given four 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 ...
5
votes
2answers
605 views

“Concave hull” - Possible? Feasible? Deterministic?

So there are several questions regarding how to compute the convex hull of a set of points. However, let's say that on inspection the set of points inscribed a star shape. A Convex hull algorithm ...
0
votes
1answer
36 views

Tetrahedron subdivision

What are all the possible subdivisions of the P3 tetrahedron (i.e. for each face, 3 vertices plus two points per edge, located at 1/3 and 2/3, and the centroïd of the face, so a total of 20 points for ...
1
vote
1answer
24 views

How to find the closest line to two segments?

I have two segments in 2D space, defined by their endpoint x and y coordinates. How can I find a best-fit line using vector algebra (formally, that minimizes the integral of square-distance from it to ...
0
votes
0answers
8 views

Rotational normalisation of a sequence using PCA

I have a 1D contour, defined as a sequence of points in 2D space. For arguments sake, lets say I want to achieve rotational normalisation by aligning the direction of the first principal component of ...
0
votes
0answers
38 views

Unique Cicum-Sphere in n-Dimensions

I want to know if there is a generic way to find the circumcenter of an (n-1)-simplex in n-dimensions. Does there a exist a unique sphere which passes through n-points in n-dimensions? For example say ...
6
votes
2answers
94 views

How to determine whether a point is inside a closed region or not?

Take the following parametric equation of an implicit curve as an example: $$ \left\{\quad \begin{array}{rl} x=& 9 \sin 2 t+5 \sin 3 t \\ y=& 9 \cos 2 t-5 \cos 3 t \\ \end{array} \right. $$ ...
0
votes
0answers
36 views

Relation between parallel transport and Jacobi field II

Before I asked a question here: Relation between parallel vector field along a geodesic and Jacobi field along that same geodesic The current question is related, and actually arise from numerical ...
2
votes
1answer
95 views

Algorithm to compute whether a stabbing line exists for a set of line segments

Let $S$ be a set of n segments in the plane. A line $L$ that intersects all segments of $S$ is called a traversal or stabber of $S$. Give an $\mathcal{O}(n^2)$ algorithm to decide if a stabber for $S$ ...
6
votes
3answers
115 views

Way to measure the similarity/difference of 2D point clouds

i need a way to measure the similarity or difference of two point clouds? The number of points in each point cloud can be different. The Point clouds are already aligned. By similarity I mean the ...
0
votes
1answer
27 views

finding volume of an n-dimensional pyramid numerically

In my experiment I need to compute hypervolume/area from a set of points, let's start with a base case -- Triangle: In this case, I have 3 points in a 2D space and they make a triangle, $p_1 = ...
0
votes
1answer
16 views

Voronoi diagram of a set of vertices of a mesh.

i have a triangulated mesh. I have some vertices which are part of the vertices of the mesh. Is there any algorithm to compute the voronoi diagram of these set of vertices. The triangulated mesh ...
1
vote
2answers
53 views

Tetrahedra from it's inscribed sphere

I'm facing a geometrical problem: Given a sphere S, I want to calculate the vertices of the tetrahedra T whose inscribed sphere is S. In other words I want to calculate a tetrahedra from it's ...
1
vote
2answers
106 views

Circumcenter of Tetrahedron (in 4D)

I am trying to calculate the circumcenter of a tetrahedron in 4 dimensional space. Basically what I am looking for is the center of the smallest sphere which passes through all 4 vertices of the ...
2
votes
0answers
42 views

Compute volume of the tetrahedron from circumsphere test

I'm working on a computational geometry algorithm. In every iteration I solve the matrix below, where (a,b,c,d) are the vertices of a tetrahedron, and e is an arbitrary point. Solving the determinant ...
0
votes
0answers
6 views

Equalize length of 1-ring edges of vertex

My question is how to equalize the length of edges in 1-ring neighbours of while-circled vertex in the below figure Hope to see your answer!
1
vote
0answers
81 views

Find the intersection between two convex hulls, in this specific case

We work over $\mathbb{R}^K$. Let $V$ the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$, . Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
-1
votes
2answers
426 views

How to get the third point coordinates in isosceles triangle?

Isosceles triangle $ABC$ $AB = AC = d_1$ $BC = d_2$ $A = (x_1, y_1)$ $B = (x_2, y_2)$ $C = (x_3, y_3)$ $\angle BAC = \phi$ $\angle ABC =\angle ACB = \theta$ I want an equation for $x_3$ and $y_3$ ...
19
votes
6answers
2k views

Is it possible to solve any Euclidean geometry problem using a computer?

By "problem", I mean a high-school type geometry problem. If no, is there other set of axioms that allows that? If yes, are there any software that does that? I did a search, but was not able to ...
0
votes
0answers
13 views

Prove Theorem with Groebner Basis

I'm trying to prove some theorems using Groebner Basis (as described in Cox, Little and O'Shea Link ) The mentioned book gives as an excercise to prove Pappus theorem using the given methodology, ...