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
0answers
31 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 ...
-1
votes
0answers
10 views

geometric modelling-bezier curves [closed]

homework: please help to solve this- Let P0(1,3), P1(4,6), P2(5,1) and P3(2,1) are the four control points of a cubic Bezier curve. Determine the end tangent vector.
10
votes
3answers
152 views

is there an efficient algorithm for comparing collections of points?

Let's say you have two sets of M points $p_1...p_M$, and $q_1...q_M$, which reside in $\mathbb{R}^N$. Is there an efficient (e.g. polynomial in M and N) algorithm to determine if the point-sets are ...
0
votes
0answers
19 views

How to test for a polygon witn n vertices if it's nonintersecting polygon or not?

How can you design an algorithm to know if an n-vertex polygon nonintersecting ? On what criteria is the test going to be
0
votes
2answers
27 views

How to compute surface normal pointing out of the object

An object has been approximated by a lot of triangles. Given the vertex positions of these triangles, how can I compute the normal of these vertices which pointing outside of the object. I know the ...
2
votes
1answer
208 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 ...
3
votes
2answers
667 views

Lat/Long grid points covered by projecting rectangle onto sphere

Before my question proper, a little background: I'm wanting to optimise some computer rendering by eliminating the drawing of things that aren't visible given the current view. Suppose we have a ...
0
votes
2answers
462 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 ...
2
votes
2answers
1k 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?
5
votes
1answer
200 views

How to determine surface from given normal vectors and their distance on that surface

Situation: We have a bendable, non-stretchable surface, like a piece of cloth, with a regular grid on it. Unknown manipulation of the surface is done while preserving it's structure We recieve 3 ...
1
vote
1answer
60 views

Find equation of line without using division

I need an algorithm to find equation of a line without using division. Given a line by two points on it, with coordinates: $(x_1, y_1),\ (x_2, y_2)$. We can simply get the line equation by the ...
0
votes
1answer
19 views

Using cartesian coordinates how to get the segment overlapping two lines/segments?

There must be an algorithm to find the coordinates of the segment overlapping (fully or partially) two lines/segments but my googling does not produce any significant result. Maybe I don't use the ...
0
votes
0answers
29 views

Is there a way to compute the empty area between a group of touching polygons?

Given a bunch of convex polygons layed out like a house truss, is there a way to compute the empty area, or get a polygon for each of those "holes" between the polygons? I tried starting from any ...
2
votes
0answers
85 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 ...
1
vote
1answer
41 views

T-shaped polygons

Is there any coefficient that can indicate T-shaped polygons ? Examples of T-shaped polygons:
0
votes
2answers
168 views

distance between a polytope point and a polytope vertex

How to find distance in between any polytope point to the closest vertex of the polytope (the verteces of the polytope are known)? How to find a distance from the farest polytope point to the closest ...
3
votes
1answer
89 views

Poisson point process (PPP) and Voronoi cells

Say we have a homogeneous PPP with rate $\lambda$ in the 2-D plane $\mathbb R^2$. In one realization of the PPP we get the points $\phi=\{x_1,x_2,...,x_i,...\}$. Now we generate the Voronoi cells ...
1
vote
2answers
37 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 ...
0
votes
0answers
34 views

Computationnal geometry: vector, basis, point and coordinate system?

I am trying to build a small geometrical library in C++, that is mathematically consistent (not so false). The goal here is to construct two concepts: vectors and points. I am not sure that the ...
1
vote
0answers
35 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 ...
-1
votes
1answer
49 views

Rotate the Points on a Plane $P = ax+by+cz + d = 0$ parallel to $z = 0$ plane

I have a plane $P = ax+by+cz + d = 0$ and many points on that plane. I want to rotate $P$ so that it becomes parallel to $z = 0$ plane. Which method should I use? I know that the normal vector of my ...
1
vote
0answers
11 views

Mapping optimal sensor placement problem to Art Gallery Problem

I am trying to design an algorithm for optimal sensor placements in a given area. I researched in this domain and found ...
0
votes
1answer
50 views

Transforming a circle to get a parabola

On http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/geometry/geo-tran.html I am unable to understand the following point Obviously, this transformation sends (x,y,w)=(1,0,1) to (x',y',w') = ...
2
votes
2answers
37 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 ...
1
vote
3answers
1k views

Given a tetrahedron, how to find the outward surface normals for each side?

Say I have a triangle in $3$D space. I can get the surface normal by calculating the vector cross product of two of the edges. But, lets say I make this a tetrahedron. How can I work out the outward ...
0
votes
0answers
27 views

Surface comparison using the vertex information and normal vectors

I have two point clouds with normal vector information. How can I use the normal vector information to measure the surface similarity of these two point clouds?
0
votes
0answers
15 views

Is there a well known algorithm for efficiently computing the vertices of a convex polytope?

A convex polytope, the one I'm talking about, is the hull around all points $x$ satisfying the matrix equation $Ax = b$ and $x \geq 0$. I've been digging around old papers from the 60's and 70's ...
3
votes
2answers
54 views

Finding point on ellipse equally distant from two other points on the ellipse

I have an ellipse with two points on it: A and C (with known coordinates). Point O is the center of the ellipse (coordinates are given). I need to find coordinates of point B which also lies on the ...
0
votes
0answers
53 views

Estimating the geometric shape of a point cloud without using the vertex information

Consider a point cloud format that describes 3D point clouds by vertices, triangle labels and normal vectors. If we miss the vertex information, is it possible to retrieve the lost data by triangle ...
3
votes
3answers
620 views

Finding the major and minor axis vertices for an ellipse given two conjugate diameters?

I've been googling, searching forums and looking in my old algebra/trig books to try to understand how to find the end points to the major and minor axis of an ellipse given the end points of two ...
5
votes
2answers
227 views

Test for intersection of two N-dimensional ellipsoids

Let's say I have two $N$-dimensional ellipsoids: $$ \sum_{i=1}^{N} \frac{(x_i - b_i)^2}{c_i^2} = 1 $$ $$ \sum_{i=1}^{N} \frac{(x_i - b'_i)^2}{c_i'^2} = 1 $$ How can I tell if the two ...
0
votes
1answer
34 views

Desargues Theorem with integer coordinates

Desargues' theorem involves a set of ten points in a plane or in three-dimensional space. (It's true in higher dimensions, but the affine span of the ten points involved never has a dimension more ...
1
vote
1answer
14 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 ...
2
votes
1answer
103 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 ...
4
votes
1answer
159 views

Convex hull problem with a twist

I have a 2D set and would like to determine from them the subset of points which, if joined together with lines, would result in an edge below which none of the points in the set exist. This problem ...
1
vote
1answer
113 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 ...
3
votes
0answers
495 views

Circle Packing Algorithm

I have question related to circle-packing. The problem is to find the circle of minimum radius enclosing four non-overlapping circles of arbitrary radius. I have to write a program in C for this ...
0
votes
2answers
34 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 ...
1
vote
2answers
105 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
50 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
59 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
1
vote
0answers
26 views

Geometric accuracy analysis of 2d rectangular models

I have reconstructed set of rectangular objects lie on a 2D plane (for ex. ABCD). All these objects are in a one coordinate system. On the other hand, I have reference models for all of them ...
4
votes
0answers
60 views

Shortest closed loop containing all extreme points of a convex set

Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. ...
1
vote
1answer
76 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
0answers
50 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 ...
0
votes
1answer
47 views

Circumsphere of a tetrahedron undefined?

I am trying to find 3D alpha shapes from my data-set. In doing so, I am keeping only those tetrahedra that have circumradius below a certain threshold. However, while finding the circumradius of the ...
1
vote
0answers
32 views

Background required for Computational Geometry

I am hoping to enroll in Computational Geometry course this spring. This was the textbook used for the course in the past. I am trying to figure out if I have required math background for this ...
1
vote
0answers
66 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 ...
0
votes
1answer
56 views

Problem while constructing Delaunay triangulation

At the moment I'm implementing an algorithm to construct a Delaunay triangulation for a set of points. I'm using the algorithm described in Computational Geometry: Algorithms and Applications. The ...
77
votes
20answers
14k 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?