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 ...
0
votes
0answers
29 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
29 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, ...
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
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 ...
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} & ...
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
25 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 ...
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 ...
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 ...
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(...
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
27 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 ...
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
34 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
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
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
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, ...
0
votes
1answer
19 views

Representing results of CSG operations with spline-based surfaces

I've been playing with a few different CAD programs and have become interested in the math involed with CSG and spline-based surfaces. During my research, I found that the curve representing the ...
3
votes
2answers
57 views

Largest four line segments of polygon

I have some polygon (see darkblue contour): It consists of very small segments, pixel by pixel, so angles differ although they seem to be the same. Visually we see 4 large line segments. How can I ...
1
vote
2answers
114 views

NURBS Curves to Interpolate Points and Derivatives on a Surface of Revolution

Problem in Prose My starting point is a set of conic segments on a plane. Each of these conic segments interpolates between three points and known slopes on the two outer points. I want to find a ...
0
votes
1answer
30 views

On applications of Alexander's Theorem

I would like to know a bit about applications of the Alexander Theorem from Knot and Braid Theory. I would be very interested in learning about possible applications for the description of everyday ...
1
vote
2answers
37 views

Given a band of $m$ opaque squares arranged in a circle, can we find a viewpoint from which we see exactly $m/2-1$ squares?

Given a band of $m\ge 3$ opaque squares arranged in a circle, can we find a viewpoint (i.e. a point on a sphere centered at the midpoint of the circle with a radius large enough to see the whole band ...
0
votes
1answer
36 views

Minkowski sum and Polygons

The problem:.. Given two convex polygons $A$ and $B$, we can define Minkowski sum as A + B = {a + b: a $\in$ A, b $\in$ B}, where $a + b$ vector sum. Prove that: every vertex $p \in A + B$ is a ...
0
votes
0answers
18 views

Visible faces of a polyhedron $P$ on a path of viewpoints on the unit sphere looking at the center of $P$

Let $P$ be an opaque polyhedron. Assuming parallel projection, let's define a viewpoint to be a point on the unit sphere around the center of $P$. Let's say that two viewpoints $v_1$ and $v_2$ are ...
1
vote
1answer
26 views

Prove that for any n > 3 there is a set of n point sites in the plane such that one of the cells of Voronoi diagram(P) has n − 1 vertices

I am trying to solve some exercises of the book "Computational Geometry Algorithm and Applications, 3rd - de berg et al" of chapter 7 - Voronoi Diagrams. Unfortunately, I am not sure if I understand ...
1
vote
1answer
60 views

Minkowski sum and vectors

Problem: Given two convex polygons A, B, we can define Minkowski sum, as A + B = {a + b: a $\in$ A, b $\in$ B}, where a + b vector sum. Prove that: for every external perpendicular u to an edge of A,...
0
votes
1answer
30 views

Number of fragments into which a fixed triangle is cut in the 3d version of the binary space partitioning algorithm

You can scroll down the question, if you're familiar with the construction of a 3d binary space partition as presented in the book Computational Geometry: Algorithms and Applications by Mark de Berg ...
1
vote
1answer
23 views

Why is no analysis possible for the 3d version of the random binary space partioning algorithm?

Let $S$ be a set of $n$ non-overlapping line segments in the plane $\ell(s)$ be the line which contains $s\in S$ $\ell^+$ and $\ell^-$ be the half-plane above and below of a line $\ell$, ...