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

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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
111 views

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