# Questions tagged [computational-geometry]

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

856 questions
Filter by
Sorted by
Tagged with
1 vote
36 views

### Find maximum sized rectangle on a plane

I'm given a rectangular plane with width, height and a set of rectangles defined by left, <...
42 views

### Shortest path in polygon from 2 points such that entire polygon is visible

Given an isothetic polygon (sides parallel to the x-axis or y-axis) and 2 points (start and end) on the boundary of the polygon, find the shortest path traveling only in the direction of the x or y ...
1 vote
19 views

### Computing the centroid of an "ellipsoid slice"

I want to compute the centroid of a body of the following form: $$E\cap H_1\cap \cdots \cap H_T$$ where: $E$ is an ellipsoid in $\mathbb{R}^d$: $E = \{x = c + Bu | u^T u \leq 1\}$, where $c$ is the ...
37 views

### Related papers about finding longest vector(maximum in magnitude) as subset sum from given set of 2d vectors [duplicate]

Given a set of 2D vectors. Find maximum magnitude of sum of a subset of the set. I want to do my undergrad thesis on this topic. Can anyone suggest me some existing papers related to this topic or its ...
1 vote
14 views

### How to avoid global delaunay check in conforming triangulation?

I implemented a conforming (i.e. it creates Steiner points using Ruppert's algorithm) delaunay triangulator, which is working, but there is one step I am doing that I straight up don't understand and ...
1 vote
26 views

### How to actually implement ruppert's algorithm?

I have been scouting the internet for resource son how to properly implement Ruppert's algorithm and what I ahve found is always lacking in details. The best resources I have so far are these 2: ...
1 vote
39 views

### Fast measurement of distance from point to mid segment?

Say you have a segment defined by 2 points $a,b$ and a third point $p$. You want to know the distance from $p$ to the midpoint of the edge. This is very straightforward: $$d = \|\frac{a + b}{2} - p\|$$...
44 views

### Finding the Point with Maximum Distance from the Boundary of a Closed Polygon in 2D Euclidean Space

Given a closed polygon defined in the 2D Euclidean plane. My objective is to determine the point within this polygon that is furthest away from its boundary. In other words, I want to find the point ...
31 views

### compute the intersection of two polytopes and it's corner points

I am looking for a method in python/matlab to calculate the corner points of polytope which is an intersection of a polytope with half spaces. I have a polytope P1 of the form -1<= x0 <= 1 -1&...
25 views

### Detailed exposition for proof of Localization Lemma in paper "Random Walks in a Convex Body and an Improved Volume Algorithm"

I've begun reading the paper "Random Walks in a Convex Body and an Improved Volume Algorithm" by Lovász-Simonovits ('93). Although the paper for the most part is pretty self-contained and ...
76 views

### Matching points on a plane with maximum total weight

I have a set of points $P = \{p_1, \dots, p_m \}, \; 0 \le m \le 10^4$ on a plane of two colors (red and green). Each point has integer x-coordinate (all x-coordinates are different), and non-negative ...
201 views

### An efficient way of finding the closest point of a sampled function to another point

I have a function $f(x)$, has been sampled into a sequence $$y_0, y_1, ..., y_{n - 1}$$ at points $x_k = k \Delta x$. $f(x)$ is neither smooth or monotone. Under this assumption, what is the fastest ...
76 views

### Efficient algorithm for finding a point P with the highest winding number

Given an ordered list of two-dimensional points $P$ that represent the vertices of an $N$-sided (very) self-intersecting polygon, find a point $p_{best}$ with the highest winding number of all points ...
34 views

### Trajectories with collisions

Say that I have a plasma gun: It's easy to compute the trajectory of the plasma ray starting from the gun. However, another ray may come from afar: As everybody knows, plasma rays are deviated when ...
1 vote
37 views

### Given a set of railroad tracks of certain shapes, find all closed tracks that can be build with it

Imagine having a number of straight and curved train track segments (e.g. 90° to the left and right, but they could have other values in the general case), how is it possible to find all complete (...
24 views

### How to enforce convexity of triangulation output?

I implemented an incremental Delaunay triangulation algorithm. It basically works except it has this weird issue. The algorithm starts by creating a bounding triangle that it then splits recursively ...
1 vote
36 views

### Detecting non-airtight geometry

I have a finite region of 3D space that some (arbitrarily-shaped, concave) geometry occupies, and I need to identify whether that geometry forms a closed 3D volume (or multiple disjoint closed 3D ...
34 views

### Data Structure for Positioning Non-Overlapping Rectangles Into Grid

I'm trying to implement a very crude form of the css grid layout. It's layout algorithm is as documented. “sparse” packing (default behavior) Set the column-start line of its placement to the ...
1 vote
77 views

### Matching the segments of a set to longer segments of another set

Consider a set $S$ of segments in the plane. Split each segment in $S$ into a few pieces, and slightly modify the extremities of each obtained segment (by adding a small random value to their ...
20 views

51 views

### Does there always exist an optimal solution to the metric steiner tree problem which doesn't contain any steiner nodes?

Given an undirected graph with nonnegative edge weights and a partition of the vertex set into terminals and Steiner vertices, the Steniner tree problem consists in finding a minimum weight tree in ...
870 views

### Multi-line fitting problem

Given a set of n points, and a number k decide whether there exist k straight lines such ...
32 views

### Generalizing the de Casteljau algorithm to cubic Bézier curve trisection

Splitting the Bézier cubic defined by the four control points $P, Q, R$, and $S$ in two parts corresponding to the two parametric subintervals $[0, t]$ and $[t, 1]$ is relatively easy: we perform ... 85 views

### Finding 2 points that are k'th closest and their distance is minimal among such points with Chebyshev distance

Let $p_1,p_2 \dots p_n$ be $n$ points in 2D such that $p_i= ( x_i,y_i)$ Let $d(p_i,p_j)= \max (|x_i-x_j|,|y_i-y_j|)$, or better known as Chebyshev distance. Find a point $p_i$ such that the distance ...
32 views

### Translating math notation from paper into something more accessible to a layman

I have been struggling trying to understand this differential geometry paper: https://cseweb.ucsd.edu/~alchern/projects/MinimalCurrent/MinimalCurrent.pdf I would like to ask for someone with more ...
26 views

### Topologizing boundaries in 3D space

I have a set of closed curves (not convex, not planar) in 3D. The goal is to produce A mesh (any will do) that is manifold and contains the closed curves as boundaries/holes. For example like this ...
111 views

### How to handle coplanarity in convex hull?

I implemented the $O(n^2)$ convex hull algorithm. That is: Find a triangle known to be in the hull (by finding the lowest point, a point connected to it in the 2D convex hull, and the point that ...
Consider $N$ points that are located on a 2D plane where the $i$-th point’s location is denoted as $(x_i, y_i)$. Is there any efficient algorithm that can compute $d_i$ that is defined as the number ...