# Tagged Questions

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

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

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 ...
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 ...
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 ...
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 * ...
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 ...
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; ...
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 ...
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.
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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$)?
84 views

### Given $n$ points in a plane, how would I find an equally-spaced collinear triple (if it exists)?

Additionally, what is the most efficient way I could do this?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
53 views