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

Rotate circle about line if a point on circle is on the line

I'm working with unit-distance graphs in $\mathbb{R}^3$, so all points are in $\mathbb{R}^3$ and points $x$ and $y$ are adjacent (notation: $x \sim y$) if and only if $|x-y|=1$ (where $|x-y|$ denotes ...
0
votes
0answers
14 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
22 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
6 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
24 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
5 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
16 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.
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 ...
0
votes
0answers
16 views

finding equation of a planes of frustum

i have a frustum and i have 4 components for each plane of a frustum, first 3 components stands for a normal to that plane and last component is its distance from the origin. I have another frustum of ...
0
votes
0answers
18 views

Minimum bounding rectangle is aligned with the convex hull

To start off, here's the problem I'm trying to solve: Suppose we have a finite collection of points in 2D. We would like to find the minimal bounding rectangle (MBR) for these points. By definition, ...
0
votes
0answers
29 views

Distance Geometry Problem (DGP) Programming Language Recommendation

We have been studying DGPs in clinic recently and I was hoping I might be able to get recommendations for computing languages in the processing of large network solutions. Specific computations ...
0
votes
0answers
25 views

3D mesh segmentation simple algorithm

I am developing the algorithm reported in this article: Lest square conformal mapping Here is presented an algorithm to flat a 3d mesh on the parametric space, but i don't understand the ...
0
votes
0answers
14 views

Proof for non-tetrahydralizability of Schonhardt polyhedron

It is established that not all polyhedrons are tetrahydralizable. Schonhardt's polyhedron is the simplest example for it. I was reading the proof for this given in the book "Art Gallery Theorems and ...
0
votes
0answers
20 views

Intersection Multiplicity of Rational Plane Curves

Suppose I have two rational curves in the complex projective plane. I know their parametrizations, $<x_1(t),y_1(t)>$ and $<x_2(t),y_2(t)>$ I know I can use Grobner bases to find an ...
0
votes
0answers
22 views

Most efficient way of transforming from V-representation to H-representation

What is an efficient way to transform from the v-representation of a convex hull (in terms of vertices) to its h-representation ($Ax \leq b$)?
0
votes
0answers
82 views
0
votes
0answers
45 views

Area swept out by a moving polygon

Say you've got a polygon (say a quadrilateral) that is moving along a certain known path in a plane. The polygon may be changing in shape as it moves, however you know the paths of each of the ...
0
votes
0answers
16 views

Reference request: quantifying qualities of a bunch of points using statistics derived from their Delaunay triangulations

I am interested in using Delaunay Triangulations (DTs) to explore the statistics of a cluster of points. Here's an example cluster of points $P$, with its $DT(P)$ (for now, ignore the difference in ...
0
votes
0answers
9 views

Find Maximum Density of Point Set

Suppose I have $n$ 3D points. Given any point $x$, radius $R$, and integer $k \leq n$, I can efficiently return a list of (up to) $k$ points nearest to $x$ and closer than $R$ (i.e. bounded k-nearest ...
0
votes
0answers
24 views

number of points with distance $\ge \delta$ that can fit inside a square with edge length $\delta$

I want to prove the claim that if you have a square with edge length $\delta$ and you want to fit as many points, each pair has distance $\ge \delta$, inside that square, You can fit at most 4, and ...
0
votes
0answers
22 views

Tangent Plane of two polyhedron from below in 3D

The convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X. A polyhedron (plural polyhedra or polyhedrons) is a solid ...
0
votes
0answers
25 views

how to find a tetrahedron in $R^n$ to bound an ellipsoid (again in $R^n$)

Assume you are given the following ellipsoid in $R^n$: $E: (c+\sum_{i=1}^n \alpha_ix_i)^2$, where $x_i$ 's are the coordinate variables. c and $\alpha_i$'s are constant. now the question is how to ...
0
votes
0answers
18 views

Boundary points of a convex hull

I have $n$ points $x_1,\dots,x_n\in\Bbb R^d$. What is an efficient way to get (some) subset of boundary points out of them? Also, if I add a new point to this set, how can I efficiently update this ...
0
votes
0answers
34 views

Rigid circles inside a square

There are $n$ circles each of radius $r$. They are needed to fit into a square with side length $t$ in a way such that, the circles can't move in any direction (each one is adjacent to some other ones ...
0
votes
0answers
10 views

What line-polygon clipping algorithm can I use to ensure that the resultant endpoints are always within the polygon?

I have a 2D plane, partitioned into n-sided, convex polygons. I'm using WRF's PNPOLY algorithm for polygon inclusion to ensure that a point belongs inside one and only one polygon. Is there an ...
0
votes
0answers
27 views

Fencing $n$ points while keeping minimum distance $d$ from each point

Consider this problem **I have a land consisting of $n$ trees. Since the trees are favorites to cows, I have a big problem saving them. So, I have planned to make a fence around the trees. I want ...
0
votes
0answers
53 views

The number of facets of an affine image

I have a full dimensional polyhedron $P_1 \subseteq \mathbb{R}^d.$ Now i define another polyhedron as follows: $$P_2 = AP_1 \oplus B$$ with $A \in \mathbb{R}^{(d-1) \times d}, \,\, B \in ...
0
votes
0answers
17 views

Natural neighbor interpolation

Recently I am interested in Natural neighbor interpolation, that is : Given a function $P(x)$ and some interpolation points $\{x_i,P(x_i)\}_{i=1}^N$, we have the interpolation function ...
0
votes
0answers
52 views

Determining N d-points yielding equal sums of Euclidean distances from M s-points

Given M source points (s-points), determine N, the number of destination points (d-points), and their locations (coordinates), such that the sum of the N Euclidean distances from each source point to ...
0
votes
0answers
35 views

Determing the Two Closest Vertices a Point Lies Between on Circumcircle

For a computational geometry application, I need to determine the two closest vertices that a point lies between on a circle that has been sliced into angular intervals. To illustrate the problem, ...
0
votes
0answers
80 views

how to compute horizontal angle of a pixel from a computer vision camera

My program needs to compute the angle of a pixel from a computer vision camera that has 120 degrees horizontal field of view, and resolution of 640 pixels wide and 480 pixels high. Program receives ...
0
votes
0answers
20 views

Finding the initial facet in giftwrapping

I'm struggling to understand how to find an initial facet via the giftwrapping algorithm. I understand that you start by taking a vertical hyperplane $H_1$, and seeing what point(s) it hits first on ...
0
votes
0answers
29 views

Extension of Isovist concept for a point - to Isovist for a polygon

There is the concept of Isovist/Visibility polygon. They both talking about volume of space visible from a given point in space. My question: What is the algorithamic solution of this problem for a ...
0
votes
0answers
15 views

Integrate gaussian over general simplex

I need to compute the volume of an $n$-dimensional simplex where some dimensions are distributed uniformly and some normally. Can this be approximated well in polynomial time?
0
votes
0answers
112 views

Relation between farthest pair of points and closest pair of points in plane

I am writing program for obtaining distance between shortest and farthest pair of points among the given points in plane .I am able to calculate them both the shortest one using divide and conquer ...
0
votes
0answers
15 views

Rotational normalisation of a sequence using PCA

I have a 1D contour, defined as a sequence of points in 2D space. For arguments sake, lets say I want to achieve rotational normalisation by aligning the direction of the first principal component of ...
0
votes
0answers
61 views

Relation between parallel transport and Jacobi field II

Before I asked a question here: Relation between parallel vector field along a geodesic and Jacobi field along that same geodesic The current question is related, and actually arise from numerical ...
0
votes
0answers
39 views

What is the mathematics behind the two animations?

I found two animated GIFs from a designer's website, which looks very impressive: My questions are: what is the mathematics behind them? How to obtain the mathematical formulas and equations of ...
0
votes
0answers
68 views

What is the shape of the set of integer sided acute triangles with largest side n?

I played around with Gauss circle problem and found that if you take a certain sum in reverse and "in forward" and subtract the resulting sequences you get the OEIS sequence: https://oeis.org/A247588 ...
0
votes
0answers
109 views

How to use CVX to solve this problem?

I have a function in the variables $x_{kl};\ k,l=1\ldots,m$, $$\sum_{i=1}^n \sum_{j=1,j<j'}^{N_i}\left( b_{ij} b_{ij'}- \sum_{k,l=1}^{m}x_{kl}f_k(a_{ij})f_l(a_{ij'})\right)^2$$ where ...
0
votes
0answers
40 views

Finding the vertices of a square giving the mid point and radius

I'm a programmer with terrible mathematics skills, but I'm getting by with studies. I'm trying to find out the vertices (x,y) of a square, giving the ...
0
votes
0answers
38 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
45 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 ...
0
votes
0answers
58 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 ...
0
votes
0answers
52 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
351 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
0answers
69 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
71 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 ...
0
votes
0answers
39 views

Is there a way to compute the empty area between a group of touching polygons?

Given a bunch of convex polygons layed out like a house truss, is there a way to compute the empty area, or get a polygon for each of those "holes" between the polygons? I tried starting from any ...