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
3answers
122 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
171 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
354 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
60 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 ...
2
votes
1answer
163 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
55 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
87 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
77 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
118 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
584 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
129 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
135 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
86 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
39 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
49 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
242 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
503 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 ...
2
votes
1answer
82 views

How to find out the control function of a cosine wave with sinusoidal input?

I have a system which is sampling at 100Hz. my input is sinusodial. The output is similar to cosine waveforms with varying frequency. I have no clue how to find out the exact formula to put into the ...
2
votes
1answer
532 views

Calculating volume of convex polytopes generated by inequalities

I have a set of inequalities, I am looking for a way to compute its volume. More specifically, I would like to compute the ratio of its volume with the volume if some more inequalities were added. I ...
2
votes
1answer
169 views

Finding the intersections of straight lines

Given a set of lines intersecting the quadrant with $x, y>0$, what are the available algorithms for finding the area below all straight lines (including $y$ and $x$ axis)? In other words, methods ...
2
votes
2answers
136 views

Did I write the right “expressions”?

$9$. Consider the parametric curve $K\subset R^3$ given by $$x = (2 + \cos(2s)) \cos(3s)$$ $$y = (2 + \cos(2s)) \sin(3s)$$ $$z = \sin(2s)$$ a) Express the equations of K as polynomial ...
2
votes
1answer
104 views

Algorithm for Identifying Convex Kernel

What algorithms currently exist to determine the convex kernel of any low-dimensional set, especially a planar set? Also, if one exists, what research has been done on it and are there any references ...
2
votes
2answers
322 views

Finding an appropriate axis of rotation for two points such that they can be rotated and translated to overlay a given line

I have two lines with known parametric equations and some number of distinct points along each line. I would like to rotate the points on $L_2$ some number of degrees $\theta$ along one and only one ...
2
votes
1answer
226 views

What is the most accurate method to get intersection point in 3D?

I have been given 3D point data, belonging to different planar segments. Points are not exactly laid on the planes so that I have fitted best planes using least square solutions. Now, I want to find ...
2
votes
1answer
476 views

alpha shapes for polygonal boundary detection - for point cloud data

i am trying to implement alpha shape algorithm but the theories is quite hard to undestand. so, if any one know (or have) pseudo codes to implement alpha shape (2d) algorithm please post us. thanks
2
votes
1answer
214 views

Need line generalization method like Dougles Peuker, that is able to keep turning points along closed polygon boundaries (for 2d or 3d point data)

I have set of point clouds, representing boundaries of different closed polygons. These polygons contains 3d points. But they also can be considered as a 2d case once boundary points are projected to ...
2
votes
2answers
779 views

Fitting data to a portion of an ellipse or conic section

Is there a straightforward algorithm for fitting data to an ellipse or other conic section? The data generally only approximately fits a portion of the ellipse. I am looking for something that doesn't ...
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 ...
2
votes
0answers
52 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
0answers
33 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 ...
2
votes
1answer
46 views

Bounding Sphere for Two Hyperrectangles

Please see the image for best illustration of the task. I have two hyperrectangles, $\text{R1}$ and $\text{R2}$, whose exact location and size is arbitrary. Now, my task is to construct a bounding ...
2
votes
2answers
118 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
0answers
28 views

Efficient algorithm for calculating hypervolume

Given a $d$-dimensional hyperrectangle that spans from the origin to the integer coordinates $l_1,l_2,l_3,\cdots,l_d$. If $V$ is the hypervolume of the solid formed by all points in the ...
2
votes
0answers
75 views

Similarity of Polyhedra: What is the measure?

When comparing two convex polyhedra, how can one determine if they are geometrically similar. Is there any algorithm to determine if one is the distorted or truncated version of the other? Vertex, ...
2
votes
3answers
70 views

Number of layers in nested convex hull

Find the maximum number of nested convex hull
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$ ...
2
votes
1answer
162 views

Modify the closest-pair algorithm to use the $L_\infty$ distance.

I'm trying to understand the closest pair of points problem. I am beginning to understand the two-dimensional case from a question a user posted some years ago. I'll link it in case someone wants to ...
2
votes
0answers
15 views

Link and its Intersection

Let $K$ be a simplicial complex in $R^2$ such that $|K|$ is a simple polygon with inside. An internal edge $ab \in K$ is an edge such that both of its two endpoints a and b are NOT on the boundary of ...
2
votes
0answers
93 views

How do I most efficiently find the perpendicular distance from a point to the convex hull of a collection of circles?

I have a collection of one or more line segments for which I know the (x,y) coordinates of the endpoints. The segments may or may not be parallel and may or may not intersect. Each segment endpoint ...
2
votes
0answers
121 views

Best closed convex surface fitting N points in 3D

First. It's easier to understand the problem by describing the application where it arises from. We have a convex body $B$ in $\mathbb{R}^{3}$ and measure points on its surface. The measurements are ...
2
votes
0answers
66 views

How many edges is sufficient to check to prove polyhedron convexity?

Consider the set $\{u_{1}, u_{2}, \ldots, u_{n}\}$ of points on the spere in $\mathbb{R}^{3}$ (i. e. $||u_{i}|| = 1$) and their convex hull C = $Hull(u_{1}, \ldots, u_{n})$. It's obvious that each ...
2
votes
2answers
63 views

How to make sure that a given set of points lie on the boundary of a possible square?

Given a set of integral coordinates , check whether all the points given lie on side of a possible square such that axis of the square so formed lie parallel to both X-axis and Y-axis . Suppose ...
2
votes
2answers
111 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
0answers
90 views

Higher Order Voronoi Diagram of a Poisson Point Process: What do we know?

This question is looking for probabilistic results of the Voronoi diagrams of 2-D space when the points are distributed by a homogeneous Poisson point process. The results can be the distribution of ...
2
votes
0answers
70 views

Generalization of Minkowski's theorem

I would like to prove a generalized version of the Minkowski's theorem, but I don't quite know how to do it. Here is what I would like to prove: Let $X\subset \mathbb{R}^d$ is convex, symmetric ...
2
votes
0answers
85 views

Orthogonal 4-cut of a convex polygon

Given a convex polygon with N vertices I need to cut it into four equal area parts with two straight orthogonal cuts. I feel that I have all the necessary pieces to solve this puzzle, but I can't put ...
2
votes
1answer
82 views

A method to test for uniform distribution over a convex polytope

Assuming I have a convex polytope defined as the intersection of $Ax=b$ and $x>0$ and I have a way to sample points from this object, is there a way I can test for uniformity of these sampled ...
2
votes
0answers
145 views

RANSAC line fitting (3d) by line segments (3d)

I am having many 3d line segments. some of them are nearly parallel and some are oriented in to different direction. I want to avoid outliers and to get the best line 3d to represent the given ...
2
votes
0answers
128 views

Calculation of the fundamental group from triangulations

Is there - say, for a triangulable surface - a concrete algorithm how to calculate the fundamental group of the surface from a given triangulation, seen as a graph (of its 1-skeleton), given as an ...
2
votes
0answers
70 views

Finding the smallest nonzero vector perpendicular to $\vec v$ with integer coordinates

Let $\vec v\in\mathbb Q^n$. Is there an efficient algorithm to compute the smallest (in the $\ell_\infty$ norm) nonzero vector $\vec w\in\mathbb Z^n$ such that $\vec v\cdot \vec w=0$? Equivalently, if ...