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

0
votes
0answers
25 views

Is there a 4 pointed star that is regular?

I am studying about the area of a 4 pointed star, I wonder if there is really a 4 pointed star that is regular? what could be the characteristics of a regular 4 pointed star?
0
votes
1answer
33 views

How to calculate volume and surface area of three dimensional figures given set of three dimensional coordinates?

I have set of three dimensional coordinates, and the shape is unknown. I would like to calculate the surface area and volume for these coordinates approximately. What is the right approach to solve ...
0
votes
1answer
17 views

Geometry (Convex Polygons)

Let P be a set of points in the plane. Let P1 be the convex polygon whose vertices are points from P and that contains all points in P. Prove that this polygon P1 is uniquely defined, and that it is ...
1
vote
2answers
30 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 ...
0
votes
0answers
35 views

Can a polygon with minimal perimeter self-intersect?

Recipe. Do the following. Throw $N$ random points $(x_0,y_0),(x_1,y_1),x_2,y_2),\cdots,(x_{N-1},y_{N-1})$ in the plane.Define $(x_N,y_N)=(x_0,y_0)$ : enumeration is $\mod N$ . These points are joined ...
0
votes
0answers
13 views

How get the new location of co-planar vertices oriented by the direction vector?

How am I supposed to get the new location of co-planar vertices, if I know the starting and ending point of direction vector, so the direction vector, in spatial space? The original vertices are in ...
2
votes
1answer
25 views

Good data structure for hyperbolic tiling

Say you're doing something computational where each data point is a tile in a (not necessarily Euclidean) 2-dimensional tiling, for instance, a Life-like cellular automata. You might want a data ...
2
votes
0answers
12 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 ...
5
votes
1answer
59 views

What series of 'hyperpolyhedrons' do exist? Is there an effective way to derive their cross-sections by 3-d subspace?

There are two obvious series of 'hyperpolyhedrons'. 'Hyperoctahedron' with vertices $(\pm1,0...0), (0,\pm1,0,...0)...(0,...0,\pm1)$ and each vertex connected by an edge with each other vertex ...
0
votes
0answers
35 views

finding quadilaterals from given sides

I have a set of Points. I triangulated the Points as delaunay triangles but i only have edges for the triangles means edge array of the whole set of Points. Now i need to find the traingles and ...
6
votes
2answers
53 views

Simplest graph that is not a segment intersection graph

Given a finite collection $S=\{s_1,s_2,\ldots,s_n\}$ of straight-line segments in the plane, their intersection graph $G(S)$ is a graph that contains a vertex $v_i$ for each segment $s_i\in S$, and an ...
0
votes
1answer
12 views

Optimized collision check for all pairs using bounding volume hierarchy

I am working on broad-phase collision detection. I understood how to build a bounding volume hierarchy using AABB's as bounding volumes. I also understood how to check all collisions of a single AABB ...
0
votes
1answer
22 views

Divide set of points by a plane so sum of distances of points on either side of plane is equal

I have a finite set of points A and another point C. I would like to compute a vector N so that the plane defined by C (point on plane) and N (normal of plane) divides all points in A with the sum of ...
0
votes
1answer
40 views

Cut the Cake into 4 parts

I'm facing the following problem: I'm given a set of coordinates on an integer grid that define the vertices of a polygon. The polygon is guaranteed to be convex. It's proven that such a polygon can ...
0
votes
0answers
18 views

Existence objective function given optimality regions

Let $I$ and $X$ be finite, nonempty sets, and denote by $\Delta(X)$ the set of probability measures on $(X,2^X)$. Suppose that for each $i \in I$, we are given a subset $M_i \subseteq \Delta(X)$ of ...
0
votes
1answer
55 views

Term For Rotating 3d Vectors About a Pivot Point

What is the term for Rotating a 3d Vector about another 3d Vector (Pivot Point)? For example; if I want to move X distance from one point towards another point - the mathematical term for this ...
1
vote
1answer
26 views

What's wrong with this pseudocode for Forster-Overfelt's version of the Greiner-Horman polygon clipping algorithm?

The Problem I'm trying to understand and implement the Forster-Overfelt version of the Greiner-Horman polygon clipping algorithm. I've read the other Stackoverflow post about clarifying this ...
1
vote
0answers
27 views

Research scopes in Computational Geometry

I have taken a short a course on Computational Geometry and at present I want to do some research works of my own. Can anybody tell me about the research scopes on it? I mean, what are the active ...
-1
votes
1answer
101 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$ ...
0
votes
0answers
38 views

A continuous centerpoint of a convex spherical polygon

In discrete geometry, a centerpoint $c$ of a discrete set $S$ of $n$ points in the plane is such that any half plane containing $c$ contains (roughly) $n/3$ points of $S$. (Such a centerpoint always ...
3
votes
1answer
77 views

Finding triangulations on 2D space by projecting lower hull of 3D

So we know that we can get the Delauney triangulation of a polygon if we map all points to the 3D space such that $p'=(p.x,p.y,p.x^2+p.y^2)$, compute the lower hull of that polyhedron, and then ...
0
votes
1answer
25 views

At what extent I can use trigonometric functions and properties with parametric curves?

I have a know-how and a library about trigonometry and trigonometric operations, I would like to know if I can possibly rely on trigonometry for parametric curves too and how the trigonometry from the ...
0
votes
1answer
21 views

What is and what are the use for an “ AINV preconditioner ” or “ SAINV ”?

In an article that I'm reading there is a mention to this "thing" and I absolutely don't know anything about it, for me it could be anything. I noticed that this thing is somehow related to the math ...
0
votes
0answers
53 views

How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
0
votes
0answers
23 views

Data structure issues with incremental Delaunay triangulation

I am implementing the incremental algorithm of Delaunay triangulation with a data structure based on Faces (triangles): 3 vertex indices and 3 Neighbor indices. The issue I have is that the structure ...
1
vote
0answers
101 views

How can I define a measure of similarity between two line segments in $\mathbb{R}^2$?

I have two segments in $\mathbb{R}^2$ and I would like to define a measure of similarity between the two segments. My idea is that I can apply: a scale transformation $s$ in order to equate the ...
0
votes
3answers
53 views

Where is the interior of the polygon?

There is an axis-parallel (orthogonal) simply-connected polygon given as a list of corners. How can I know whether a certain vertical segment has the interior of the polygon on its east or on its ...
5
votes
1answer
77 views

filling an occluded plane with the smallest number of rectangles

I've got a specific problem which I'll try to describe as clearly as possible. I have a defined rectangular region on a cartesian plane, and within that region there are other given rectangular ...
6
votes
1answer
78 views

Putting fence around sheep

Convex hull algorithms are well known. However, in my case, the goal is slightly modified: Given $N$ points in a plane, construct convex polygon with minimal area so that it contains all points, and ...
0
votes
1answer
45 views

Formula of signed distance from hyperplane to point

Let $H$ be a hyperplane defined by the points $p_1, p_2, ..., p_n$ and single point $x$ generally out of the hyperplane. Is there any formula to calculate the signed distance between $x$ and $H$? I ...
1
vote
0answers
19 views

Traveling Salesperson tour monotonicity

Prove that the travelling salesperson tour TSP of a set S of points is monotone, that is, if S ⊆ S′, then the length of TSP(S) is less than or equal to the length of TSP(S′).
0
votes
1answer
44 views

Avoiding gimbal lock

I am not really sure if I understand the phenomenon of gimbal lock correctly. Say I have a vector $\begin{pmatrix} x\\ y\\ z \end{pmatrix}$. And I want to keep the vector's length fixed but move it ...
1
vote
2answers
35 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 ...
0
votes
1answer
14 views

Applications of logarithmic functions in shapes and geometries

As I understand this logarithmic functions are a family of functions where the equation for $f(x)$ is written like so $$\begin{align} f(x) = & \log_{a} x \\ & \mathtt{where\ }a\mathtt{\ is\ ...
2
votes
2answers
78 views

Given four points, verify if they form a Tetrahedron

As per the title, I've been requested to build a program that -given 4 points in space- determine if they form a 3D shape and if this is case to present it's volume. For the volume part of the ...
8
votes
2answers
210 views

Visual illustrations of circle packing theorem?

Circle packing theorem states: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G. Paper Collins, Stephenson: A circle ...
2
votes
1answer
53 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
2answers
129 views

What is inside and outside of complex polygon?

I am reading this paper http://arxiv.org/pdf/1207.3502.pdf Given a complex polygon. Its edges may intersect. The algorithm finds out if given point is inside of polygon or not. It draws a line from ...
0
votes
2answers
52 views

Why are rectangular cartograms hard to generate?

I was reading this paper on rectangular cartograms - ...
1
vote
1answer
51 views

Prove that volume of a ball in a polytope is very small

An exercise in a book asks to prove that for a bounded convex polytope $P\subseteq\mathbb{R}^n$ defined as an intersection of $k$ closed halfspaces and for a unit ball $B^n$ contained in $P$ the ...
0
votes
0answers
23 views

Schwarz–Christoffel-like mapping on differentiable simple cubic spline boundary

For a concept of a computer game I have in mind I came to need that. I have a 2D pond, which has a boundary that is a simple differentiable cubic spline. There are ducks floating around, looking at ...
0
votes
1answer
34 views

Altitudes of Triangle

I have a triangle defined as 3 lines, each defined by two coordinate points A and B. I have the area of the triangle but need to calculate the 3 altitudes and their respective sides A and B points. ...
2
votes
1answer
71 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 ...
1
vote
1answer
114 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.
2
votes
1answer
47 views

Collinear points in 3dimension

Given three $3D$ points: $A,B$ and $C$, what is the procedure to check if they are collinear? In general, given $n$ points in $m$-dimension, how should one find out, if these $n$-points defines a ...
2
votes
0answers
60 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 ...
0
votes
1answer
33 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
12
votes
3answers
158 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 ...
1
vote
1answer
72 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
43 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 ...