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
1answer
10 views

General algorithm to cap an n-dimensional convex polyhedra

I am looking for a way to cap an $n$-dimensional ($n$ > 3) polyhedra, that is to say: Given an $n$ dimensional set of vertices and faces (including hyperplane equation), and an $n$ dimensional ...
3
votes
2answers
76 views

Test if point is in convex hull of $n$ points

I have $n$ points $x_1,\dots,x_n\in\Bbb R^d$, and I would like to check that some other point $y$ lies in their convex hull. How can I do this in some efficient way? I think that there was an ...
4
votes
1answer
223 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 ...
0
votes
0answers
28 views

$\;\oint H(x) \, \delta(y) \, dy = \frac{1}{2\pi} \oint d\phi\;$ : crossing number = winding number?

A point in the plane is something without size. We can consider instead a fuzzyfied point, smeared out over a small domain in the plane. Cast in more mathematical terms: a point at $(0,0)$ is a Dirac ...
0
votes
0answers
28 views

How to estimate the maximum projection area of a set of spheres?

I have a set of spheres P. The spheres have a known, finite range of radii. It seems that there must be at least one 2 dimensional plane such that the bounding circle around the projection of P onto ...
1
vote
0answers
15 views

Extension of Planar Algorithms to Higher-Dimensional Voronoi Diagrams

Voronoi diagrams are not new, and there are many established algorithms (Fortune's, Lloyd's) for generating them (or their duals, the Delaunay triangulation). There are many recent-ish papers too, ...
2
votes
1answer
561 views

Finding points on ellipse

I have ellipse in 2D. I want to compute fixed number of points on this ellipse with constant angular separation between those points. My first idea was to generate line equations from center of the ...
0
votes
0answers
43 views

Finding shortest vertical segment connecting two sets of intersecting half-planes

Consider two sets of $n$ half-planes each. Denote the sets by $A$ and $B$. How can we find a vertical segment $s$ of a minimum length such that the upper end of $s$ is in the intersection of $A$ and ...
0
votes
1answer
44 views

Inscribing convex polygon within simple polyon

Suppose you are given a simple (but not necessarily convex) polygon $C$ and a point $p$ inside this polygon. I have a particular way of inscribing a convex polygon $I$ within $P$, and I would like to ...
0
votes
0answers
31 views

Smallest enclosing cylinder

I have a set of 3D points that approximately lie on a cylinder. This cylinder is straight and can be oriented in any direction. I would like to compute the minimal enclosing cylinder for the set; that ...
4
votes
1answer
111 views

Find closest point, subject to linear inequality constraints

Given a point $p\in \mathcal{R}^2$, I want to compute the closest point $x \in \mathcal{R}^2$, subject to linear inequality constraints $Ax \leq b$. That is, $$\begin{array}{ll} \text{minimize} & ...
0
votes
1answer
26 views

formula to find radius of circle from polygen vertex of semicircle [closed]

I am looking for formula to compute the radius of circle using the given polygen vertex information of a semicircle. i.e Give information Polygen vertex (a,b,c,d,e). When i connect the vertex its ...
-1
votes
0answers
14 views

Contour lines to discrete heighmap

I looking for a way to convert contour lines (representing height of a landscape) to 2.5 height map (a 2 dimensional array where each value represents the heigh of a given position). What is the best ...
0
votes
0answers
40 views

Fastest point-plane distance in $R^3$

Many questions regard computing the point-plane distance, my question in borderline with computer science, though. What is the fastest way of computing in $R^3$ the point-plane distance, with ...
3
votes
0answers
51 views

Hyperplane Problem

Given $M$ points in $\mathbb{R}^{N}$, (where $M$ is larger than $N$) I was wondering if there is an approximation algorithm to find a hyperplane which goes through the origin and also intersects as ...
3
votes
2answers
90 views

Simplifying polygons

I want to turn digitized polygons into simpler shapes. More precisely, given a noisy closed polyline, I want to fit a polygon to it with an imposed number of sides, such as a triangle or ...
2
votes
1answer
59 views

Largest enclosed (inscribed) circle in cloud of points

I have a set of points that approximately lie on a circle. I would like to compute the largest circle that does not contain any of the points. Of course, one could draw the circle far away from the ...
2
votes
0answers
69 views

Optimal convex hull that maximizes # points from set A and minimizes # points from set B

This problem arose in a computer vision hobby project. Say I have two sets of points in three dimensional Cartesian space: A and B. The problem I would like to solve is to find the convex hull V of ...
0
votes
0answers
24 views

Inverse projection matrix 2D to 3D

I am writing a simple computer vision application in which reports the position of coloured dots on the floor. The floor is observed by a camera for which I have the correct projection matrix. I.E. If ...
1
vote
0answers
38 views

split a rectangle with triangles into polygons as uniformly as possible

Given a rectangle $A$ and $n$ triangles $\{B_1,B_2,...,B_n\}$, I put the triangles inside $A$, at least one vertex of each triangle is not outside $A$ (inside $A$ or on the edge of $A$). So that A is ...
-1
votes
2answers
59 views

Intuition behind the formula of convex combination of two distinct points

A convex combination of two vertices $p = ( a, b )$ and $q = ( c, d )$ is any point $r = ( e, f )$ such that for some $x$ in range $0 \le x \le 1$, $e = xa + ( 1 - x )c$ and $f = xb + ( 1 - x )d$. ...
0
votes
0answers
14 views

The meaning of “order of congruence” of metric space

I was studying low-distortion embedding of finite metric space, and was confused about the following concept: Order of congruence: A metric space $(X,D)$ has order of congruence at most $m$ if every ...
5
votes
4answers
478 views

Algorithm to find the point in a convex polygon closest to an external point

Given a convex polygon $P$, and a point $q$ of the plane, external to $P$, what is the fastest algorithm to compute the closest point in $P$ to $q$? A linear algorithm of course works, computing the ...
1
vote
1answer
32 views

Determine 2D Convex Hull given 3D Convex Hull

Suppose I have a discrete set of points $S \subset \mathbb{R}^{3}$ and I am given the points which belong to the convex hull of S, $CH(S)$. Without loss of generality, let us assume that I project the ...
0
votes
0answers
14 views

Find regions of a polygon where maximum horizontal internal line segment is $\leq r$ for some $r\in\mathbb{R}$

I'm hoping someone can help me with the following problem. Consider a simply-connected, closed polygon $P$ (possibly non-convex). Let $R = P_1,P_2,\dots,P_n$ be some partition of $P$, and let $\ell(...
2
votes
2answers
853 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 ...
1
vote
0answers
34 views

Given a number N, how to construct a set of different numbers that has a maximal product, and the sum of these numbers equal N?

Note that: N is positive integer. The set also consists of positive integers. The set consists of different integers. (The thread suggested by @hardmath doesn't have this constraint.) For example: ...
0
votes
0answers
19 views

Orient a non-planar closed curve

I wasn't sure whether to post here or on Stack Overflow, but here seemed more appropriate. Please let me know if I have to move the question. In a 3D app I have a non-planar closed curve that is ...
0
votes
1answer
34 views

Voronoi edges example

I have 4 line segments: 0 0 2 0 // 1st line segment 2 0 2 1 // 2nd line segment 2 1 0 1 0 1 0 0 and I wrote some CGAL code to print the Voronoi edges. However, <...
0
votes
0answers
26 views

Finding the number of integer points inside a sphere of radius R and dimension D centered at the Origin

I am writing a computer program to count the number of integer points inside a sphere of radius R and Dimension D centered at the origin. In essence, if we have a sphere of dimension 2 (circle) and ...
0
votes
0answers
18 views

Similarity measure for uncertain point sets

Imagine that we have two sets of points $M=(x_{1}, x_{2},...x_m)$ and $N=(x_{1}, x_{2},...x_n)$. These are actually lists of $x$, $y$ (and $z$) in 2D (or 3D) space so $x_i\in\ \mathbb{R}^2$ (or $x_i\...
1
vote
0answers
19 views

computing the heat kernel for small times

The heat kernel on a two-dimensional manifold $M$ has the well-known expression $$H(p,q,t) = \sum_{i=1}^\infty e^{\lambda_i t}\phi_i(p)\phi_i(q)$$ where $\phi_i, \lambda_i$ are the eigenfunctions and ...
0
votes
0answers
34 views

Query about hyperplane in SVM

I am a beginner in Machine Learning. I was reading through basics of SVM and read this definition: The goal of a support vector machine is to find the optimal separating hyperplane which ...
2
votes
1answer
78 views

Area of Convex hull

For every point set $A \subset R^2$, prove that in general the sum of the coordinates of $\phi(T)$ is independent of a triangulation T and is associated to the area of the Convexv_Hull(A). We define ...
1
vote
0answers
29 views

Is there an equation/algorithm to find the axis of a curved helix with varying pitch and radius?

I'm trying to find a way to numerically extract or estimate the axis of rotation for an arbitrarily shaped helix, which may be curved and have varying pitch and radius. (See here for an example.) ...
1
vote
1answer
17 views

Given a ray and line segment, compute radius of smallest circle satisfying certain criteria

Given a ray and a line segment, (efficiently) compute the radius of the smallest circle satisfying the following criteria: The circle contains the origin of the ray. The center of the circle lies on ...
0
votes
0answers
16 views

Find 2 point getting far away each other from their intersection point

I want to know how to find 2 aircraft getting far away from their intersection point, from Dataset such as aircraft 6-7,11-2, 10-6,37-36,etc. Dataset: my algorithm is: calculate direction ...
11
votes
2answers
12k views

Point closest to a set four of lines in 3D

Given four lines in $3D$ (represented as a couple of points), I want to find the point in space which minimizes the sum of distances between this point and every line. I'm trying to find a way to ...
1
vote
0answers
46 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
24 views

Show that the intersection between a polygon and convex hull can be computed in the O(n+m)

I am trying to understand triangulation, explained in the book "Computational Geometry Algorithms and Applications, 3rd Ed - de Berg et al". Unfortunately, I don't know how to solve the following ...
0
votes
0answers
23 views

Shatter coefficient and VC dimension of a grid in $R^d$

Given $\epsilon>0$, partition the cube $[0, 1]^d$ with square of side length $\epsilon$. The total number of square in the partition is $$ N = \left(\frac{1}{\epsilon}\right)^d. $$ What is the ...
0
votes
0answers
7 views

Given M points and a weighted graph G, map the vertices to distinct points to minimize sum(edge_weight*edge_length)

Given an arbitrary undirected weighted graph G with N vertices, and an arbitrary set of M points P in euclidean 3-space, where M>=N, map the vertices to distinct points such that sum(edge_weight * ...
0
votes
0answers
7 views

K-Server Problem on a Unit Square

How does a K-Server clustering look on the set of all points on the unit square? It clearly must be equal to a Voronoi diagram almost everywhere, but what is the configuration of cluster centers and ...
0
votes
0answers
33 views

Rectangle-Rectangle Intersection Area - Area Only

Suppose I have two rectangles that are not necessarily axis-aligned. What is a fast way to calculate their intersection area? Note that I am aware of convex polygon intersection and area algorithms; ...
0
votes
0answers
14 views

Bottleneck Distance Significance?

Let $X$ be a smooth manifold and $f,g:X\rightarrow \mathbb{R}$ two real valued functions on $X$. Suppose we have two persistence diagrams $Dgm(f)$ and $Dgm(g)$ encoding the lifetime of $k$-dimensional ...
0
votes
0answers
29 views

What is bottleneck distance intuitively?

Can someone explain the intuition behind Bottlneck and Wasserstein distance? The context here is the comparison of two persistence diagrams.
1
vote
1answer
253 views

Determining if a set of hexagons on a grid can tile the plane

Suppose I have a regular grid of identical hexagons that tile the plane, that is a hexagonal lattice. How can I determine if a connected subset of these hexagons (i.e. a poly-hex) can tile the plane ...
9
votes
1answer
309 views

Optimal bounding boxes selection for $N$ rectangles

Suppose that I have $n$ straight rectangles on a plane $r_i = (x_i,y_i,w_i,h_i)$. Each rectangle has a cost function, its area $A(r_i) = w_i \cdot h_i $. I can also "merge" 2 or more rectangles into ...
1
vote
0answers
25 views

Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
3
votes
0answers
165 views

How can I find a maximal inscribed ellipsoid to a *concave* set of points, in 3D?

I have a set of points which describe the surface of an irregular, natural (i.e., occurs in nature) object. This point set is not necessarily convex, and contains occasional indentations so parts of ...