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

1
vote
1answer
111 views

Algorithm to compute mesh from intersection of infinite halfspaces

Is there a simple algorithm to compute the convex polyhedron (as a mesh with verticies, edges, and faces) resulting from the intersection of a set of infinite halfspaces? This is essentially a CSG ...
1
vote
2answers
175 views

Handling points to get closed Cycles

I have set of line segments, containing only 2 points. I know their point numbers. some point numbers are appeared in many lines according to their connections. So, when joining some end points, I can ...
1
vote
1answer
85 views

Cutting a d-simplex

Why is it possible to get any possible subset of nodes of a d+1 simplex in IR^d using halfspaces?
1
vote
1answer
219 views

Algorithm to Choose Consistent Normals for All Faces on a Polyhedron

I have a polyhedron $P$, in 3D, which consists of $f$ faces, each face consists of $V$ vertexes. My question is, how to choose a consistent normal orientation for all the faces? Consistent here means ...
1
vote
1answer
435 views

Using Chazelle's simplicity test to verify simple polygons intersection

Is there a way to verify whether a non-empty intersection exists between two simple polygons (not necessarily convex) using the Chazelle's simplicity test ?
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 ...
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
60 views

Convex hull solving using a rubber band?

The convex hull can be found by stretching a rubber band so that it contains all the points and then releasing it. So my question is : lets assume that we have a robot (a theoretical robot) to solve ...
1
vote
1answer
36 views

Why simple polygons in plane have this property?

If we are given a simple polygon $P$ in the plane by the points $A_1, A_2, \dots, A_n$. How can we prove that there are $3$ consecutive points $A_i, A_{i+1}, A_{i+2}$ (if $i = n$, for $A_{i + 1}$ and ...
1
vote
2answers
41 views

Determining points on a circle in a particular plane

This is more of a computer graphics question really, but I was just wondering the efficient way to determine n equally spaced points on a circle, given a normal vector to the circle and the radius of ...
1
vote
1answer
357 views

Equation of hyperplane in Matlab

Given $n$ points in $n$-dimensions, using MatLab, how should we find the equation of the $(n-1)$-dimensional hyperplane passing through these $n$ points.
1
vote
1answer
22 views

find set of points for lots of triangulations

I should find a set of $n$ points $Q$ in a plane, so that $t(Q)$ (the number of possible triangulations) the following equation holds: $$t(Q) \ge 2^{n-2\sqrt{n}}$$ I solved the problem using the ...
1
vote
1answer
129 views

Calculate base and coefficient for power curve through 3 non-linear points

I have a formula that takes a 0-based bounded single dimensional input and transforms it to a specific power curve. EDIT This is single dimensional. There is no $y$. In the image, I'm showing how ...
1
vote
1answer
225 views

3D Convex Hull and The Gift Wrapping Principle

I am currently trying to implement a 3D convex hull algorithm that is based on the paper Convex Hulls of Finite Sets of Points in Two and Three Dimensions by F.P. Preparata and S.J. Hong, but I’ve run ...
1
vote
1answer
94 views

When is a convex polygon inscribable?

Defining the diameter of a convex polygon as the maximum possible distance between all pairs of vertices, can we conclude that the convex polygon is inscribable (i.e has all its sides as chords of a ...
1
vote
1answer
225 views

What is the typical method for sampling uniformly in a convex polytope

The polytope in my case is the intersection of the k-plane $Ax=b$ and $\{x>0\}$ where $A$ is the constraint matrix and $b$ is some solution. I'd like to find a method that is fast and efficient for ...
1
vote
1answer
62 views

What do we call the angular arcs between two edges of triangles?

I've been trying to find a geometry library for java which is as high level as describing angles between adjacent sides of triangles given 3 sides. So, what do we call such kind of arcs. In many ...
1
vote
1answer
130 views

angle between steepest gradient of two plane

IF I have two 3d planes such as Oab and Oa'b'. If these two planes intersect a horizontal plane and the intersection of each plane makes AB and A'B' lines. then, Does the angle between AB, A'B' ...
1
vote
1answer
167 views

Steepest slope gradient of a vertical plane

I know the steepest slope gradient (Azimuth) of a 3D plane can be obtained by projecting normal vector onto XY Plane. So, when the plane is slant, the steepest gradient will be a some value. ...
1
vote
1answer
93 views

Diagonal of a convex polygon such that the obtained cuts have simmilar areas

Let $P$ be a convex polygon represented with a list of vertices specified by some orientation. Consider the following problem Problem. Find in linear time a diagonal of $P$ such that the absolute ...
1
vote
1answer
304 views

Hausdorff Distance Between Convex Polygons

I'm interested in calculating the Hausdorff Distance between 2 polygons (specifically quadrilaterals which are almost rectangles) defined by their vertices. They may overlap. Recall $d_H(A,B) = ...
1
vote
1answer
72 views

Polygon: Internal Rays

Suppose I have an arbitrary non-self-intersecting polygon. I want to generate a list of points which lie on the edges of this polygon according to the following procedure: I iterate over each edge ...
1
vote
1answer
228 views

Testing polygon monotonicity

I am looking for an idea of an algorithm for the following problem: Give an efficient algorithm to determine whether a polygon P with n vertices is monotone with respect to some line, not ...
1
vote
1answer
176 views

Algorithm for Triangulation Dual Tree

I am looking for algorithm for the following problem. Given a list of diagonals of a polygon forming a triangulation, with each diagonal specified by counterclockwise indices of the endpoints, ...
1
vote
1answer
123 views

Convex Hull in Hierarchy Structure

As a beggining to convex hull algorithms lecturer introduced the structure which it's called "Hierarchy Structure". Hierarchy Structure: in every given convex hull there is a maximum size convex hull ...
1
vote
1answer
77 views

Determine if two polyhedrals are the same shape and if so, map their vertices

I have a polyhedron and want to determine whether it is combinatorially equivalent to another polyhedron. I know how many faces comprise each polyhedron and for each face, I know all of its vertices, ...
1
vote
1answer
209 views

Computing surface normal, floating point arithmetic

If I have a $n$-gon in $\mathbb{R^3}$, and I want to compute the surface normal, how can I get a value that minimizes error in a floating-point system? For example: Would I gain accuracy by first ...
1
vote
1answer
233 views

Ancient astronomers, planetary conjunctions, and epicycles

How did ancient astronomers predict planetary conjunctions? I know they used a system of epicycles to represent the path of planets, but finding the point and time of alignment of two planets still ...
1
vote
2answers
980 views

Check if point on circle is in between two other points (Java)

I am struggling with the following question. I'd like to check if a point on a circle is between two other points to check if the point is in the boundary. It is easy to calculate when the boundary ...
1
vote
1answer
90 views

Line segment k-intersection

Could you please help me to design the following algorithm: I have a random-access list of line segments defined by a pair of points $[x^s_i; x^e_i]$. The list is initially unsorted, but of course ...
1
vote
1answer
237 views

Cover a polygon using a minimal set of rectangles

Given some polygon and rectangles all of a fixed height and width, how I can calculate the number and placement of the rectangles so that no point within or on the polygon is not contained within at ...
1
vote
1answer
265 views

Intersection of two sectors

Is there algorithm that decide if two sectors intersect? I can transform the sector into polygons and use standard algorithms, but it has some cons. Any other ideas?
1
vote
1answer
601 views

3 line / 3 plane intersection

I am confused on a very simple thing, so I need your clarifications. Here is my doubt: I want to find the intersection point of three straight lines. Alternatively, I can find it by using three ...
1
vote
2answers
214 views

Calculating probabilities on a spherical map

A black and white colored sphere is given. We are looking at a random starting point on the sphere below us, which has a certain color. A random rotation can change the color of the spot below us. ...
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 $= ...
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 ...
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 ...
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
vote
0answers
22 views

Find largest regions bounded by a set of planes

Suppose we are given a set of planes that partition the unit cube into a large number of regions. Is there a computationally efficient way to find the region with the largest volume?
1
vote
0answers
54 views

Understanding BlowUp Computation in Singular

Many of us might know that "Singular" is a computer algebra system for Algebraic Geometry, Commutative Algebra and Non-commutative algebra. This is a procedure in "Singular" for computing blowups. ...
1
vote
1answer
94 views

What is a composition of two binary relations geometrically?

the composition was defined as follow: (a,b) \in (R;S) <=> there is c | (a,c) \in R and (c,b) \in S . If our two relations R and S are two convex polygon ...
1
vote
0answers
41 views

population of dots with normal distribution of pitch

I want to generate a plot that shows a rectangle populated with dots, where the dot-to-dot distance (pitch) distribution is a lognormal (or a gaussian). I want to be able to change the mean dot-to-dot ...
1
vote
0answers
25 views

Finding other two vertices when one vertex and each point on the triangle is known ?

I am working on some gesture recognition for my game. I am stuck on a problem. I have one vertex i.e the starting point and every point on the triangle, I also have the centroid. So how do I find the ...
1
vote
0answers
26 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than 2 I should choose a special partitioning hyperplane for the divide and conquer algorithm to get O(n log n). I am confused because to choose this ...
1
vote
0answers
58 views

Find 3D concave hull based on original model and convex hull

I want to find the concave hull of a 3d model, with a threshold for the maximum edge size. Googling around let me to the following approach (mainly abstracting from 2d approaches): Determine the ...
1
vote
0answers
35 views

Geometric Median

Is there a relationship between Voronoi Diagrams and the geometric median? I know that it is impossible to find a closed expression for the geometric median, but the two concepts seem related.
1
vote
0answers
16 views

ellipsoid and paraboloid relation

My task was to programme a paraboloid and an ellipsoid. I implemented paraboloid as a set of points that's distance from the focal point and the distance from the plane is the same. After running the ...
1
vote
0answers
130 views

How to Compute the Torsion and Curvature of a Parametric Curve

So I have a parametric curve $\bf{r}=${$x(n),y(n),z(n)$} such that the functions $x(n)$, $y(n)$ and $z(n)$ are polynomials of $4$-th degree. I have several of these curves, and I want to calculate the ...
1
vote
2answers
164 views

Determinant (computational geometry)

Let p=(px,py),q=(qx,qy), and r=(rx,ry).Show that the sign of the determinant |1 px py| D=|1 qx qy| |1 rx ry| determines whether a point r lies to the ...