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
7 views

The number of Binary Search Tree that exist with same Postorder and Inorder

how many BST exist with same postorder and inorder traversal? I know that in binary tree (Not BST), it is one. but i have a book from that said for BST it is CATALAN number. i become confused.
0
votes
0answers
6 views

How to compute Convex hull of set points from voronoi diagram

Assume $n$ points in the plane and their Voronoi diagram are given, prove that the convex hull of the points can be computed in linear time.
1
vote
1answer
19 views

Convex hull solving using a rubber band?

The convex hull can be found by stretching a rubber band so that it contains all the points and then releasing it. So my question is : lets assume that we have a robot (a theoretical robot) to solve ...
4
votes
0answers
45 views
+100

Fast search of local positive quadruples on the sphere

Let $U = \{u_{1}, u_{2}, \ldots, u_{n}\} \subset \mathbb{R}^{3}$ be the finite set of points on the unit sphere in $\mathbb{R}^{3}$: $||u_{i}||_{2} = 1$ Definition: Quadruple of points $(u_{i}, ...
2
votes
2answers
47 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 ...
1
vote
1answer
32 views

Why simple polygons in plane have this property?

If we are given a simple polygon $P$ in the plane by the points $A_1, A_2, \dots, A_n$. How can we prove that there are $3$ consecutive points $A_i, A_{i+1}, A_{i+2}$ (if $i = n$, for $A_{i + 1}$ and ...
2
votes
0answers
22 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 ...
0
votes
0answers
22 views

What does “maximum geometric error of a chunk” mean?

In this paper, on the top of page 7 it says, Where $\delta$ is the maximum geometric error of a chunk ... What does that mean? Thanks :D
0
votes
0answers
20 views

How to navigate around a smooth surface?

Suppose I want to find the shortest path between two points in $\Bbb{R}^3$ with smooth obstacles in the way? I understand things like Dijkstra's algorithm for shortest paths on a graph. But what about ...
3
votes
1answer
41 views

Graphing algorithm

I am not sure if this belongs on Mathematics Stack Exchange, but it is somewhat relavant here. The Problem If you've installed any graphing/plotting apps on your smartphone, you will notice that the ...
1
vote
0answers
9 views

Alternative to triple precision in line intersection computations

I often have to compute intersections of line segments using integer coordinates. The exact analytical expression involves the ratio of a third degree expression over a second degree one, and that ...
0
votes
0answers
15 views

Ways of partitioning n points into some cubes

Assume there're $n$ fixed points in $\mathbb{R}^d$ contained in a ball with radius $M$,and you can partition the space by cubic grid with cube's edge length $h>\epsilon$. How many different ways of ...
1
vote
0answers
29 views

population of dots with normal distribution of pitch

I want to generate a plot that shows a rectangle populated with dots, where the dot-to-dot distance (pitch) distribution is a lognormal (or a gaussian). I want to be able to change the mean dot-to-dot ...
12
votes
1answer
156 views

Automorphism group of a lattice's Voronoi cell

Let $\Lambda$ denote a lattice of $\mathbb{R}^n$, i.e. $$\Lambda = \left\{\sum_{k=1}^n n_i\mathbf{a}_i\ \bigg|\ n_i\in\mathbb{Z}\right\},$$ for $n$ linearly independent vectors $\{\mathbf{a}_i\}$ in ...
0
votes
1answer
24 views

How to determine if some line segments are collinear

Let's say I have several Line Segments that are connected to each other and make a Polyline. How can I determine if they are ...
0
votes
1answer
23 views

How do I place two points on two axis-aligned line segments such that they have given Euclidean distance l?

This is my problem: I am given two axis aligned line segments $l_1$ and $l_2$ of finite length and a distance $l$. How do I find points $p_1 \in l_1$ and $p_2 \in l_2$, such that $||p_1-p_2||_2 = l$? ...
1
vote
0answers
16 views

Finding other two vertices when one vertex and each point on the triangle is known ?

I am working on some gesture recognition for my game. I am stuck on a problem. I have one vertex i.e the starting point and every point on the triangle, I also have the centroid. So how do I find the ...
0
votes
1answer
19 views

Finding other two vertices of a triangle from centroid and one vertex?

I am working on some gesture recognition for my game and I want to find if a point is inside the triangle created by the user or not. For that I need three vertices. Currently I am using the '$1 ...
0
votes
1answer
33 views

Hypersphere - Pattern matching using Centroid, Radius and Diameter

I have a hyper-sphere formed with set of $n$-dimensional data points. I could calculate centroid ($X_0$), radius($R$) and diameter($D$). Using these $X_0, R, D$, how I can find whether the a given ...
0
votes
1answer
26 views

Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

Not sure whether this question belongs here or mathoverflow. You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be inside ...
0
votes
2answers
43 views

Scan line algorithm for intersecting polygons

Given two sets of polygons $P_1 = \{s_1,...,s_m\}$ and $P_2=\{s_m+1,...,s_n\}$ with total number of $n$ segments, the previous and next segment on it's polygon can be determined in $O(1)$. Describe a ...
1
vote
0answers
22 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than 2 I should choose a special partitioning hyperplane for the divide and conquer algorithm to get O(n log n). I am confused because to choose this ...
0
votes
1answer
16 views

Equality of polyhedra

Is a minimal representation for a polyhedron unique? And if so can we use this to prove that two polyhedra are equal (or maybe the same is a better definition).
0
votes
0answers
13 views

point-tuple orientation

Does something like point-tuple orientation exist? I read this book, pg 336, paragraph "One can even..." and I've bumped into this quite unfamiliar notation. Thanks for clarification. P.S. if someone ...
2
votes
1answer
38 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 ...
0
votes
2answers
90 views

Hexagonal Tessellation on a sphere

I want to detect collision of a sphere with another object and to find out(show) the deformation of the sphere. I have come to know that hexagon(regular)tessellation of a sphere is the most ...
1
vote
0answers
32 views

Find 3D concave hull based on original model and convex hull

I want to find the concave hull of a 3d model, with a threshold for the maximum edge size. Googling around let me to the following approach (mainly abstracting from 2d approaches): Determine the ...
0
votes
3answers
75 views

determine unit outward normal vector on a curve

It is necessary for me to find unit outward normal vector for the curve: $$\gamma=(x(t),y(t))$$ where $$x(t)=(0.6)\cos(t)-(0.3)\cos(3t)$$ and $$y(t)=(0.7)\sin(t)+(0.07)\sin(7t)+(0.1)\sin(3t)$$ I ...
0
votes
0answers
55 views

quadratic constraints representations

I have two surfaces of parameter $x \in \mathcal{X} \subset \mathbb{R}^n$ with $\mathcal{X}$ to be a polytope: $u(x) = ax + b \subset \mathbb{R}^m, z(x) = x^TAx + B^Tx + C \in \mathbb{R}$. If $m=1$, ...
0
votes
1answer
42 views

Convex hull of a set of points

Let $a_1,a_2...a_r \in R^n$ be points in $R^n$. Prove:$$CH(\{a_1,...,a_r\})=\left\{\sum_{i=1}^r\alpha_ia_i|\sum_{i=1}^r\alpha_i=1,\alpha_i\ge0\right\}=:K$$i.e. the convex hull of the $a_i$ is the set ...
2
votes
0answers
66 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, ...
0
votes
1answer
37 views

Convex hull is convex

A set $C \in R^n$ is called convex if the line segment $L = \{ tp + (1-t)p | 0 \lt t \lt 1 \}$ between two arbitrary points $p,p' \in C$ is contained in $C$. The convex hull $CH(C)$ of a set $C ...
0
votes
0answers
30 views

Two convex polygon intersection from set of m convex polygons with total n vertices

I have a set of m convex polygons $(p_1,p_2, \ldots p_m)$. $n_i$ is the number of vertices in $p_i$. $\sum_{i=1}^{m} n_i = n$. Each polygon has vertices listed in anti-clockwise direction, starting ...
2
votes
3answers
34 views

Number of layers in nested convex hull

Find the maximum number of nested convex hull
0
votes
1answer
27 views

Visible objects from a point in a polygon with holes in 2d

The problem is the following: Given a polygon P with h holes/objects and a point c inside P but outside the holes/objects. P has n given vertices and each hole/object h has 4 vertices (the ...
1
vote
0answers
28 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
85 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. ...
-1
votes
1answer
66 views

Find the length of each side of a square containing regular hexagons [duplicate]

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
56 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
1answer
26 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
0
votes
1answer
14 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
98 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
17 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
14 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
58 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
22 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
70 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
52 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
67 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 ...
1
vote
2answers
52 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 ...