Questions tagged [computational-geometry]

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

Filter by
Sorted by
Tagged with
2 votes
0 answers
114 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 ...
coding's user avatar
  • 121
1 vote
0 answers
20 views

Algorithm for computing $\epsilon$-packings of Sets in Euclidean Space

Let $\epsilon > 0$. For $P\subset \mathbb R^d$, a subset $Q\subset P$ is called an $\epsilon$-packing if: for every $p \in P$ there is a $q\in Q$ such that $d(p,q) \leq \epsilon$, and for every $q,...
pyridoxal_trigeminus's user avatar
2 votes
0 answers
42 views

Max min diversity on points taken from line segments in the plane

If I start with $n$ different points $P_1,\ldots,P_n \in \mathbb{R}^2$ and want to select a set $X$ of cardinality $m \leqslant n$ from them subject to the condition that the value $$d_\text{min}(X) = ...
Jürgen Böhm's user avatar
1 vote
0 answers
39 views

What are solutions to the convex hull problem?

I have researched multiple solutions to the convex hull problem, but I am afraid I don't really understand some of them. For example, Graham's scan is a bit confusing as it is not very clear if the n ...
user79644's user avatar
1 vote
0 answers
61 views

Optimal Data structure for queries involved rectangles and cartesian coordinates

What data structure would be optimal in terms of time and space for the following usecase: Given information about rectangles in the form of- {rectangle_id,left_bottom_corner_x, ...
fat_gladiator17's user avatar
1 vote
1 answer
30 views

How to topologically classify points in 3d space generating a surface?

Say I have N points sampled on a surface in 3 dimensions (ie. points on the surface of a sphere, 1-torus etc.). Is there an algorithm that would be able to count the number of holes in the surface ...
Nikolaj's user avatar
  • 11
1 vote
0 answers
26 views

ensure connectivity in geometric optimization

I am working on parts of my master-thesis and got to a problem which I would like to solve and develop some algorithm for. Basically I am dealing with 2d-geometry which I would like to represent using ...
Finn Eggers's user avatar
0 votes
1 answer
25 views

Speed up FOR loop containing CGAL's bounded side check for each 2D point

Using the CGAL library, I am working on a 2D layout graph which contains an array of 2D polygons with holes. The aim is to generate random points (based on some conditions) and only keep the points ...
Apurv Mishra's user avatar
2 votes
0 answers
57 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, <...
popcorn's user avatar
  • 73
3 votes
0 answers
44 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 ...
swastik sarkar's user avatar
1 vote
0 answers
21 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 ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
39 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 ...
Iridescent 53's user avatar
1 vote
1 answer
17 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 ...
Makogan's user avatar
  • 331
1 vote
0 answers
27 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: ...
Makogan's user avatar
  • 331
1 vote
1 answer
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\|$$...
Makogan's user avatar
  • 331
0 votes
1 answer
59 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 ...
Meni's user avatar
  • 103
0 votes
1 answer
36 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&...
Möbius's user avatar
  • 21
0 votes
0 answers
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 ...
total dependent random choice's user avatar
0 votes
1 answer
77 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 ...
Grigori's user avatar
  • 105
0 votes
2 answers
205 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 ...
user877329's user avatar
3 votes
1 answer
119 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 ...
Mark Miller's user avatar
3 votes
1 answer
37 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 ...
cdupont's user avatar
  • 131
1 vote
0 answers
38 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 (...
2080's user avatar
  • 191
0 votes
1 answer
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 ...
Makogan's user avatar
  • 331
1 vote
1 answer
42 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 ...
Alex Barilaro's user avatar
0 votes
0 answers
40 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 ...
Sentient's user avatar
  • 113
1 vote
3 answers
79 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 ...
Matthieu Latapy's user avatar
0 votes
0 answers
23 views

Getting a V-representation from an H-Representation of a polytope

I am trying to find an easy to follow resource on implementing any (reasonable) algorithm to find a V-represnetation of a polytope from its h-representation. I only need this to work for $\mathbb{R}^...
Makogan's user avatar
  • 331
0 votes
0 answers
18 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 ...
Makogan's user avatar
  • 331
1 vote
0 answers
41 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 ...
Makogan's user avatar
  • 331
4 votes
2 answers
518 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 ...
Makogan's user avatar
  • 331
0 votes
0 answers
12 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 ...
nothacking's user avatar
3 votes
2 answers
92 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 ...
Makogan's user avatar
  • 331
3 votes
2 answers
78 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 ...
Makogan's user avatar
  • 331
0 votes
0 answers
20 views

Algorithm for computing the vertices of a polytope defined as the intersection of half spaces

There's a very similarly sounding question with an answer already, but my setup is very, very different. You are given $k$ half spaces in dimension $d$, defined by a point and a direction. You want to ...
Makogan's user avatar
  • 331
4 votes
1 answer
153 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 ...
user avatar
1 vote
0 answers
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....
Leonid Dworzanski's user avatar
1 vote
1 answer
110 views

Orthogonal connectors with non-overlapping horizontal or vertical line segments

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 (...
Olumide's user avatar
  • 153
1 vote
0 answers
23 views

Matching a 2D points cloud to polylines

I have a (2D) point cloud of reasonable size (say some thousands of points) and a set of (2D) polylines also of a reasonable size. I want to assess the discrepancies between the two geometries and for ...
user avatar
0 votes
0 answers
29 views

NURB Sphere surface degree elevation and knot insertion

The code for degree elevation of curves in The NURBS Book by Les Piegl and Wayne Tiller pages 206--209(The_NURBS_Book) assumes the knot vector for the curve is given as: $$(0,...,0,...,1,...,1)$$ ...
John He's user avatar
2 votes
1 answer
81 views

Algorithm to find intersection between collection of sets

I have two dataframes representing products two distributors sell. They look like this: df1 for distributor 1. ...
nepee's user avatar
  • 280
1 vote
1 answer
205 views

How to turn a 3D polytope into a mesh?

Let us say you have a polyotpe define as the intersection of halfplanes. That is you are given N half-spaces. The polytope is the volume defined by all points which lie on the positive side of all N ...
Makogan's user avatar
  • 331
3 votes
0 answers
72 views

Minimum spanning tree between blobs

We have a binary raster image in which we consider the white blobs (connected components). We define a distance between two blobs to be the length of the shortest path between any two respective ...
user avatar
7 votes
2 answers
341 views

Queries to count points lying on arbitrary line

Suppose we have $N$ points on $XY$ plane, ie. $(x, y)$ and $x, y \in Z$ and multiple queries where each query is of the form $y = mx + c$ and $m, c \in Z$. Is it possible to count number of points ...
bihariforces's user avatar
0 votes
1 answer
49 views

Finding pixel closest (grid points) to rectilinear polygons

I have rectilinear polygons present, and they are surrounded by grids(grey rectangle with dots denoting center) as shown in the diagram below. There are some areas where grids are not present - like ...
kil47's user avatar
  • 3
2 votes
1 answer
92 views

Red-blue orthogonal line intersection algorithm

I need to efficiently find the intersections between a set of vertical line segments and a set of horizontal ones. The segments in both families can overlap (but there are no duplicates). Presumably ...
user avatar
3 votes
3 answers
162 views

Find a unit square containing most of the points

Given points $p_1,\ldots,p_n$ in $\mathbb{R}^2$, the task is to find an axis-aligned unit square containing the maximum number of points. I came up with and $O(n^3)$ algorithm as follows. Observation ...
Michal Dvořák's user avatar
2 votes
0 answers
48 views

Minimal bounding quadrilateral of a convex polygon

I am looking at the problem of finding the quadrilateral of minimum area that encloses a convex polygon. I found the following articles: An Optimal Algorithm for Finding Minimal Enclosing Triangles ...
user avatar
4 votes
0 answers
54 views

Minimum stabbing problem for a set of convex polygons

Let $S = \{P_1, P_2, ..., P_m\}$ be a set of convex polygons in $\mathbb R^2$ with a total of $n$ vertices. Polygons are defined by ordered lists of vertices, and each vertex is represented by a pair $...
HEKTO's user avatar
  • 3,078
0 votes
2 answers
55 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 ...
SVMteamsTool's user avatar

1
2 3 4 5
18