Tagged Questions

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
20 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.
0
votes
1answer
30 views

Use of Delaunay Triangulation and Voronoi Diagram to find alpha shape using Edelsbrunner's algorithm

I am learning how to find the shape of a set of points in 2-D. I understand that Alpha Shape method is a good way to find the shape of a set of points. Alpha Shape was originally introduced by H. ...
0
votes
1answer
26 views

Find the length of each side of a square containing regular hexagons

I have to find the length of each side of a square such that all the regular hexagons of same length side and radius lying inside the square have centers either inside the square or on the boundaries ...
0
votes
0answers
37 views

Mathematical proof to find the length of each side of a square filled with Regular Hexagons

I have to prove or disprove that in a square box if there are full regular hexagons( whose distance from center to every corner is r) inside it, then the centers of those hexagons should lie inside ...
0
votes
0answers
14 views

Point location( planar subdivision)

Show that, given a planar subdivision S with n vertices and edges and a query point q, the face of S containing q can be computed in time O(n). Assume that S is given in a doubly-connected edge list
-1
votes
0answers
25 views

Algorithm and Complexity: Choosing a field [closed]

I need some help with following... I study maths with specialization in CS. I take the course "Algorithm and Complexity" and I have to choose one of the fields Computer Science (the operations of a ...
0
votes
1answer
10 views

Computing the Center of Gravity of the Unit Cube + Halfspace

Consider the unit hypercube in $\mathbb{R}^N$. $\mathcal{P} = \{\mathbf{x} ~| ~x_i \in [0,1] \text{ for } i=1,\ldots,N \}$ and a half-space which intersects the unit cube: $\mathcal{H} = ...
0
votes
2answers
49 views

Sorting a list of points in 2-D clockwise

I have number of points with co-ordinate (latitude, longitude) in 2-D: Here is a collection of some points: \begin{array}{ccc} \hline No.& lon & lat \\ \hline 1& 84.07921& 24.49703 ...
0
votes
0answers
9 views

Proof of spherical Helly's theorem

I need to prove that if every three members of a system of convex sets on the surface of a sphere intersect, every member fits in some hemisphere and no four members cover the whole sphere, then the ...
1
vote
0answers
10 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 ...
0
votes
1answer
25 views

Is k-means clustering guaranteed to converge if using Manhattan distance?

The k-means algorithm is an iterative clustering algorithm that partitions the data points into K clusters (with centroids {$\mu_1, ... , \mu_k$}, minimizing the Sum-of-Squared-Error: $$ SSE = ...
0
votes
0answers
21 views

Maximal area intersection of half-planes in $\mathbb{R}^2$

Suppose we have $m$ half-planes $H_1,...,H_m$ in $\mathbb{R}^2$ such that $H_1 \cap \dots \cap H_m = \emptyset$. Let $A$ be a set of subsets $S$ of $\{H_1,...,H_m\}$ with non empty intersection and ...
0
votes
1answer
26 views

intersection of an ellipsoid and cylindrical plane.

I need to understand if an ellipsoid and a cylindrical arc intersect, what will be the general equation of the cutted ellipse? How can I solve for that equation? I know in 3D, the equation of an ...
1
vote
0answers
39 views

Algorithm to compute wether 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$ ...
1
vote
0answers
32 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 ...
0
votes
1answer
25 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 ...
2
votes
1answer
59 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 ...
1
vote
0answers
61 views

Minkowski sum of two polytopes via the halfspace representation

If i have two polytopes denoted by $P_1, P_2 \subset \mathbb{R}^d$, suppose their halfspace representations are respectively $H_1x \leq K_1$ and $H_2x \leq K_2$. Now, considering their Minkowski sum, ...
0
votes
0answers
27 views

Find points that defines the intersection of an ellipse with a plane.

I want to test for the intersection of two ellipses $E_1$ and $E_2$ in $\mathbb{R}^3$ represented on a computer. In some sense, this isn't a hard problem: ...
0
votes
0answers
48 views

Algorithm to optimize rectangles filling by rectangles

I have a set of rectangles, all of the same size (W,H) (in fact paper sheets). I have another set of n rectangles of different sizes (Wi,Hi), i = 1..n such that Wi <= W and Hi <= H (in fact ...
0
votes
1answer
54 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
19 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
54 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
43 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
16 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
32 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
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 ...
5
votes
1answer
60 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
36 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
54 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
16 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
27 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
66 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
68 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
37 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
30 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
181 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
45 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
80 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
29 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
22 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
60 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
24 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
150 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
55 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
84 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
85 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
50 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′).