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