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
1answer
422 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
164 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
131 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
98 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
309 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
215 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
391 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
195 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
612 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
57 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
24 views

Number of layers in nested convex hull

Find the maximum number of nested convex hull
2
votes
1answer
70 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
13 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
73 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
107 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
2answers
54 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
87 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
76 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
55 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
73 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
72 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
110 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
1answer
201 views

Lloyd's algorithm in normed vector spaces

How do I run Lloyd's algorithm in a normed vector space? The space: L*a*b* color space, finite sRGB segment, $R^3$ The distance metric: CIE94 using L*C*h* information derived from the L*a*b* ...
2
votes
0answers
85 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
68 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 ...
2
votes
0answers
353 views

Algorithm for Collection of Shortest Paths in a Grid without any clash at a point of time.

The efficient algorithm needs to be done and proved for the best solution for the given problem: User inputs: (#) Size of the NxN Grid. (N); (#) No. of Paths: Z; (#) Source and Destination ...
2
votes
1answer
148 views

Showing: point of polytope which maximizes the minimum distance to a vertex is a barycentre?

Let $T_1$ and $T_2$ be two regular $(n-1)$-dimensional simplices with vertices $$(t,0,\ldots,0), (0,t,\ldots, 0),\ldots, (0, 0, \ldots, t),$$ and $$(t-n+1,1,\ldots, 1), (1, t-n+1, \ldots, 1), \ldots, ...
2
votes
0answers
41 views

Terrain tile scale in case of tilted camera

I am working on 3d terrain visualization tool right now. The surface is logically covered with square tiles. This tiling could be visualized as follows: For some reason I have to know scale of a ...
2
votes
1answer
134 views

Fitting a cylinder of known length to the chord between its circular edges s.t. the cylinder's mass near a point is minimized

Let the pair of three-space coordinates $p_1$ & $p_2$ define a chord between the edges of a cylinder of radius $R_c$ and length $L$. The edges here represent the two circular borders between the ...
2
votes
0answers
651 views

Is there a formula for the solid angle at each vertex of tetrahedron?

A tetrahedron has four vertices as much as a triangle has three vertices. A tetrahedron therefore can have four solid angles as much as a triangle can have three angles. I am wondering: Is there a ...
2
votes
0answers
888 views

How to find all intersection points of two splines?

2D-Cubic splines are given in parametric form (X(t), Y(t) and X(s), Y(s)). Every segment has it's own X and Y expression. And I want to find all intersection points. Some segments are intersecting ...
2
votes
0answers
99 views

find largest cube in lot of cuboids

sorry for my bad English... I've a system consists of many cuboids, many are adjacent to the others. My problem is... I want to find the largest cube in this system (which may consists of many of some ...
2
votes
0answers
446 views

Set of segments a vertical ray intersects

The problem is 10.6a from Computational Geometry: Algorithms and Applications. We want to solve the following query problem: Given a set $S$ of $n$ disjoint line segments in the plane, ...
1
vote
4answers
321 views

What is the name for a maximal convex set of points contained in another set of points?

What is the name for a maximal convex set of points contained in another set of points X? Maximal in terms of inclusion. For the desired set to be unique, X can be restricted to be a simple polygon ...
1
vote
3answers
192 views

Finding a point above the line in $O(\log n)$

I am trying to solve the following problem. So far with no success. Let $S$ be a set of $n$ points in the plane. Preprocess $S$ so that, given a (non-vertical) line $l$, one can determine whether ...
1
vote
2answers
6k 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
808 views

Is this a wrong solution to the smallest enclosing circle problem?

I have a set of points in $\mathbb{R}^2$ and I need to find the smallest enclosing circle, i.e. the circle with the smallest radius that contains all of the points belonging to the set. I have the ...
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 ...
1
vote
1answer
130 views

Can Centroid Lies on the Edge of a Polygon?

This question is similar to the one here. Now the question is, given a simple polygon with $Area>0$, regardless of whether it is convex or concave and with no opening, can we prove that the ...
1
vote
2answers
591 views

superellipsoid: problem in understanding parametric formula

hi i've found this interesting page: superellipse and superellipsoid and i used the formula for one of my computer graphics applications. i used (the most usefull for computer graphics) the parametric ...
1
vote
2answers
107 views

How to find co ordinates of a triangle after increasing the area by a factor of $\alpha$?

i am given with a triangle $\{(x_1,y_1),(x_2,y_2),(x_3,y_3)\}$ and the area need to be increased by a factor $\alpha$. can i anyone let me know formula to find the co ordinates of new triangle? There ...
1
vote
2answers
259 views

Best fit for 'puzzle' shapes inside a frame

Consider a large rectangle frame, as we want to fill it with small rectangles with variable sizes. How to calculate the best match of inner objects to minimize empty spaces inside the main frame? ...
1
vote
2answers
38 views

Estimating the missing points of a 3D point cloud

Consider a cloud of N points (forming a smooth 3D object), in which n points are missing. Also, consider that there is no prior knowledge about the original shape of the point cloud. The only ...
1
vote
2answers
44 views

Point as an element of an affine space vs point as an element of a topological space?

I am searching for the "most natural" definition of a (geometrical/space) point as an element of "something" in mathematics (I am trying to design a small computational geometry library on strong ...
1
vote
2answers
512 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 ...
1
vote
2answers
96 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 ...
1
vote
3answers
86 views

Are there any Heron-like formulas for convex polygons?

Are there any Heron-like formulas for convex polygons ? By Heron-like I mean formulas without angles as arguments and which takes as arguments only lenghts of sides of polygon - that is - we know no ...
1
vote
1answer
146 views

Algorithm Design for Delaunay Triangulation?

I am very much happy after seeing some very good answers in this site. I am trying to design a algorithm for the construction of Delaunay Triangulation using Randomized Incremental Algorithm.(I wont ...
1
vote
2answers
2k views

Ellipse fitting methods.

I have set of points and want to fit ellipse to this set. I have found only function which fits ellipse in least squares sense. In this set of points there are some noise points which should not be ...
1
vote
2answers
185 views

Find outline of $N$ points in a plane

If I have $N$ point coordinates $P_i = ( x_i, \, y_i ) $ and I want to draw the outline connecting only the points on the "outside", what is the algorithm to do this? This is what I want to do: ...