The 2024 Developer Survey results are live! See the results

# Questions tagged [computational-geometry]

Questions about algorithmic solutions of geometric problems, or other algorithms making usage of geometry.

873 questions
Filter by
Sorted by
Tagged with
31 views

### How to generate a skeleton (medial axis) of a polygon using Fortune's algorithm?

I have been learning recently about Fortune's algorithm to generate the Voronoi diagram given some input but I was interested in the application of this within polygons to generate skeletons (also ...
• 131
1 vote
33 views

### Point- line primal, dual [closed]

The primal configuration of point $p=(a, b)$ implies non-vertical line $p^*=\{(x,y)\mid y=ax-b\}$ is dual configuration. And the primal configuration of non-vertical line $\ell=\{(x,y)\mid y=mx-n\}$ ...
• 113
46 views

### Decomposing a general polygon into simple ones

This is a question about splitting a very general kind of polygon into a list of simple polygons. Let me introduce some notions: Let an 'edge class' $E$ be a set of homeomorphic images of the unit ...
• 161
62 views

### Calculating minimum area annulus in O(n)

So given n points on a plane, I'm trying to find a pair of concentric circles so that all the points are between the circles, and that area is as small as possible, in linear time. What I'm thinking ...
• 31
1 vote
21 views

### Linear time algorithm for computing radius of membership hyper-sphere

We are given a Graph, G(V, E), where V is the node set and E is the edge set consisting of ordered tuples (u, v). The graph is undirected, as such, if (u,v) is in E, then (v, u) is in E. Alongside the ...
• 111
34 views

### Find, in linear time, a line that intersects all the segments and has the largest possible slope, or determine that there is no such line

I'm wondering how to approach this question. Let $e_1, \ldots, e_n$ be $n$ horizontal segments in the plane. Find, in linear time, a line that intersects all the segments and has the largest possible ...
• 31
43 views

### Maximum number of regions in partition induced by convex $k$-vertex polygons

I have a set $\mathcal{P}$ of $n$ convex $k$-gons (convex $k$-vertex polygons) on the (Euclidean) plane. These define a partition of the plane, or rather the plane sans the pointer on the contour of ...
• 995
18 views

### Basic illustration of universal computation in Margenstern's work on Cellular Automata in Hyperbolic Spaces

I am fascinated with these two hyperbolic tessellations, what Maurice Margenstern calls the heptagrid and the pentagrid. I have the two volumes/books he authored, but they are a bit dense for my not-...
• 2,265
61 views

### Generate random points such that no 4 lie on a circle

In $\tilde{O}(n)$ time, can I generate $n$ random lattice points so that no four lie on the same circle? You can assume we pick points from a grid of side length $k \gg n$ (say, take $k=n^2$). I have ...
31 views

### Largest Tetrahedra from a set of points

Problem Given a set of k points in 3D Euclidean space with k ≥ 4, find four points from the set that form a tetrahedra such that the volume of the tetrahedra is maximized. Attempted Solution Find ...
1 vote
26 views

### Resolving distance constraints in 2D

I am currently writing a tool that will be used in an industrial process to place components with physical requirements. It boils down to the following: I have a set of points (typically, a few ...
• 111
39 views

### Want to plot rectangles given their width,height and the cartesian origin (0,0)

The info I am given : block_ID, block_width, block_height as well as how the cuts between the rectangles are(horizontal or vertical); for example two rectangles can be joined by a horizontal cut or a ...
• 11
123 views

### Find the longest northeast path in $O(n\log n)$ time

Given a set $Z$ of $n$ points $(p_1,p_2,p_3, \ldots,p_n)$. The coordinates of these points are arbitrary numbers and are unsorted. If they give me $s$ and $t$ to be two points in $Z$. A northeast path ...
• 121
1 vote
28 views

• 341
19 views

### Implementation of algorithm to enumerate all vertices of a convex polyhedron defined as linear inequalities?

I am looking for an implementation for any of the methods to enumerate all vertices of a convex polyhedron defined by $Ax \leq b$ I have found some papers that talk about the problem, for example this ...
• 341
1 vote
43 views

### Algorithm for Steiner points?

I am trying to find resources that explain an easy to implement (not necessarily optimal but reasonable runtime) algorithm for inserting Steiner points in a triangulation. There seems to be little ...
• 341
573 views

### Detecting if an edge is "inside" a polygon?

I have computed a constrained triangulation of a set of points. The constraint happens to be a closed polygon. The objective is to detect all edges which are inside the polygon, that is, an edge where ...
• 341
14 views

### Compute the intersection and difference of multiple polygons

I have multiple (possibly concave) simple polygons, and need to compute the union and difference of them, some polygons have to be added, some subtracted from the final shape. I have found algorithms ...
166 views

### Constrained Delaunay triangulation algorithm?

I am trying to find a resource which explains how to compute the constrained Delaunay triangulation of a set of points and edge constraints, I found these slides by Jonathan Shewchuck, but without the ...
• 341
106 views

### Efficiently finding point triangle inclusion when doing incremental delaunay triangulation?

I want to implement a delaunay triangulator by using incremental building, which is purported to be $O(n \log(n))$ I am a little puzzled about 2 things. Ever resource I read on the matter says: Make ...
• 341
168 views

### Rotating sort algorithm

Take a set of $n$ points in the plane. You want to sort them by increasing abscissa. But you also want to sort them by abscissa after several arbitrary rotations, say $k$, in increasing angles. The ...
1 vote
50 views

### Are there known algorithms to find a line that intersects a given set of segments?

Are there known algorithms to find a line that intersects a given set of segments? In: A finite set of segments. Out: A line that cross all these segments or explicit answer that there is no such line....
1 vote
I have an upper row of $N$ equally spaced 'units' and a lower row of $N$ equally spaced 'units'. I would like to connect any of the upper row of units to the lower units via orthogonal connectors (...