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

Nonlinear least squares and polygon area

I found this paper that describes preserving the global area of a polygon given some deformation (section 5): http://www.kunzhou.net/publications/2DShape.pdf I'm trying to do something very similar. ...
1
vote
0answers
90 views

How to interpolate sequential points to obtain functions and/or vectors?

I would like to know how I can interpolate a sequence (time) of points in order to obtain curves as some kind of mathematical functions. Unfortunately math is not my area so I don't really know the ...
1
vote
0answers
113 views

Complexity of Counting the number of inducing $n$-gons

Definition: A $n$-gon is simple if it has no self intersection and is in general position if no pair of its edges are parallel. It is clear that by extending the edges of each simple $n$-gon in ...
0
votes
0answers
22 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 ...
0
votes
0answers
38 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
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 ...
0
votes
0answers
23 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 ...
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 ...
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(...
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
0answers
24 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\...
0
votes
0answers
33 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 ...
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
30 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
13 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.
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
19 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
32 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
40 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
18 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
24 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
84 views
0
votes
0answers
46 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
23 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
26 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
21 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
35 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
13 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 \mathbb{R}^{...
0
votes
0answers
18 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 $$P^*(x)=\sum_{...
0
votes
0answers
54 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
36 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
98 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
30 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
16 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
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 ...