Questions tagged [computational-geometry]

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

299 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
31 votes
0 answers
804 views

Largest set of cocircular points

Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior). This can be done in $O(n^3)$ ...
chubakueno's user avatar
8 votes
0 answers
114 views

Data Structures for Non-Orientable Manifolds

I am looking for a data structure to represent non-orientable manifolds (i.e. meshes like Moebius Strip, but without self-intersection). I will then implement other algorithms using this DS such as, ...
user63364's user avatar
8 votes
0 answers
2k views

Area of the union of rectangles anchored on the x-axis

I am trying to solve the following computational geometry problem. Let $S$ be a set of $n$ axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in $S$ lies on the $x$-axis....
com's user avatar
  • 3,169
7 votes
0 answers
167 views

Finding a rainbow independent set in a circle

Inside the interval $[0,1]$, there are $n^2$ intervals of $n$ different colors: $n$ intervals of each color. The intervals of each color are pairwise-disjoint. A rainbow independent set is a set of $n$...
Erel Segal-Halevi's user avatar
7 votes
0 answers
209 views

Algorithms for curve construction

I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks? ...
user3658307's user avatar
7 votes
0 answers
445 views

Minimal covering circle

There are $n<10^4$ points on the plane. How can one approximately (with a given precision $2^{-20}$ of points' coordinates) find the minimal radius of a circle that covers some $k$ out of $n$ these ...
se0808's user avatar
  • 213
6 votes
0 answers
119 views

Placing a tripod in a plane such that it partition a given set of points (with pic)

I would appreciate if anyone could help me with the following problem: Given a set of 3n points in the plane with n > 0, is it possible to find a placement of a tripod such that each region contains ...
AlgorithmUser785's user avatar
6 votes
0 answers
115 views

$3$-dimensional convex hull using only a desired number of planes

I would like to find the convex polytope with the smallest volume that envelops (contains) all the points of a given 3D point cloud and that can be constructed from only $k$ planes. This is similar to ...
balt's user avatar
  • 61
6 votes
0 answers
294 views

Extrema and saddle point of 3D field at different scales

I have a scalar 3D field $f(x, y, z)$ with $x,y,z$ on a regular grid. I would like to know the location of the maxima, minima, saddle points and their relation as a function of a smoothing scale. For ...
cphyc's user avatar
  • 161
6 votes
0 answers
630 views

Space filling between random 2D lines

Note that I had asked this question in GIS forum, although it has gotten many up-votes, still has not received any answer. Hope you can break the silence, some collaboration :) Consider a region (...
Developer's user avatar
  • 161
6 votes
1 answer
342 views

Radon transform for advanced 3d graphics and games?

The Radon transform is used to take 2d projections of an object and create a 3d representation. It seems like it would be possible to apply such a transform in 3d graphics in games (although possibly ...
Archival's user avatar
  • 171
5 votes
0 answers
58 views

Efficient algorithm to compute the Heesch number of a shape

The Heesch number of a shape is the maximum number of layers of copies of the same shape that can surround it. For example the following shape (in the center) has a Heesch number of 4, because we can ...
Dmitry Kamenetsky's user avatar
5 votes
0 answers
234 views

Finding the Hamiltonian cycle that uses the least amount of straight lines

How can i find the Hamiltonian cycle on an nxn grid that uses the least amount of stright lines (curves left/right as much as possible)? Here's an example we have devised for 8x8: Here is an example ...
Tzlil's user avatar
  • 51
5 votes
0 answers
154 views

Is Geometric Disjoint Set Cover in P?

I have come across the following optimisation subproblem: Geometric Disjoint Set Cover. Consider a collection $C$ of (not necessarily distinct) ranges taken from a universe range $X \subset \mathbb{...
D. G.'s user avatar
  • 193
5 votes
0 answers
116 views

3D mesh segmentation simple algorithm

I am developing the algorithm reported in this article: Lest square conformal mapping Here is presented an algorithm to flat a 3d mesh on the parametric space, but i don't understand the ...
Mugna's user avatar
  • 51
5 votes
0 answers
791 views

Arc-Length parameterization of a cubic bezier curve

I like to implement an arc-length Parameterization of a cubic bezier curve. So far I have implemented the method of calculating the arc length of the curve and now I'm stuck at calculating the times ...
user39558's 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
4 votes
0 answers
156 views

Find a dynamic programming solution that minimize the sum of the diameters of two clusters?

I asked a question at this link, where I suggested a greedy algorithm for this problem: Suppose given $2n$ points in the plane and we want partition points into two clusters $C_1$ , $C_2$ such that ...
All's user avatar
  • 83
4 votes
0 answers
69 views

Finding the smallest distance between a point and a set of points

I have a GPS dataset that corresponds to a route taken by a vehicle in a day. It consist of a set of coordinates. Then say I have a coordinate and I want to know how close this coordinate is to this ...
TarsEndurance's user avatar
4 votes
0 answers
125 views

Efficient 2d interval merging product

Suppose I have two tables of 2d intervals (axis-aligned rectangles) with values attributed to each interval. ...
yupbank's user avatar
  • 215
4 votes
0 answers
139 views

Find the largest interior rectangle composed of partitioning rectangles

Suppose a rectangle $R$ is partitioned into more than one smaller rectangles of positive area. What is the fastest algorithm to find the largest rectangle strictly within the all-enclosing rectangle $...
Hans's user avatar
  • 197
4 votes
0 answers
118 views

Approximation Algorithms via Unit Disk Graph Embeddings

A unit disk graph is defined by a collection of $n$ vertices corresponding to $n$ points on the plane, with an edge between any two vertices whose distance is at most $r$. Some $NP$-hard problems ...
Zur Luria's user avatar
  • 339
4 votes
0 answers
39 views

Is there a name for the class of distance functions that are compatible with k-d trees?

The typical nearest neighbor search implementation for k-d trees prunes branches when the distance between the target and the pivot along the current axis exceeds the smallest distance found so far. ...
Tavian Barnes's user avatar
4 votes
0 answers
228 views

Rectangle Packing with Constraints

I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a ...
xopticx's user avatar
  • 41
4 votes
1 answer
101 views

Can we find the largest intersecting subfamily of convex polygons in quadratic time?

Let $\mathcal{F} = \{P_1, P_2,\ldots,P_m\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (...
Tassle's user avatar
  • 2,442
4 votes
0 answers
53 views

Minimal set of inequalities including good points but excluding bad points

Suppose I have a collection of good convex sets and bad convex sets in $\mathbb{R}^d$ (where $d$ can be big). Each convex set is defined by a series of closed ranges in each dimension $d$ - a ...
orlp's user avatar
  • 12.9k
4 votes
0 answers
67 views

Randomized algorithm to compute cover radius?

I am self-study the book "Geometric Approximation Algorithms" by Sariel Har-Peled. And I stuck on a problem and don't know how to start it. Let $C$ and $P$ be two sets of point in the plane , such ...
ShaoyuPei's user avatar
  • 153
4 votes
0 answers
138 views

One-sided, distance-optimal polyline reduction to a given number of vertices

So I have been battling this rather peculiar problem: given the following input (on an euclidean plane): point p polyline l integer n p is not inside of the convex hull of l find a new polyline l', ...
user129186's user avatar
4 votes
0 answers
418 views

Partitioning rectangles

Suppose that there are rectangles in the Cartesian plane, each aligned with the axes---the rectangles are defined by left and right x-coordinates and top and bottom y-coordinates. There are two ...
Todd Proebsting's user avatar
4 votes
0 answers
30 views

Enumerating Polygonal Subdivisons

Let $P$ be a given polygon in $\mathbb{R}^{2}$ such that all the vertices lie on integral points $\mathbb{Z}^{2}$. An integral polygonal sub-divison of $P$ is a subdivison of $P$ into integral sub-...
DBS's user avatar
  • 141
4 votes
0 answers
108 views

Computing average tile size (grid)

I am trying to compute the average cell size on the following set of points, as seen on the picture: . The picture was generated using gnuplot: ...
malat's user avatar
  • 141
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
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
3 votes
0 answers
53 views

Edge length in an EMST

Consider a domain on a unit grid such that the grid nodes hold a point with probability $\frac12$. We construct a Euclidean minimum spanning tree on these points. How could we compute the probability ...
user avatar
3 votes
0 answers
381 views

Prove that the set of edges of a Delaunay triangulation of $P$ contains an EMST (Euclidean minimum spanning tree) for $P$

I was studying computational geometry on my own from "Computational Geometry: Algorithms and Applications" - by Mark de Berg. In chapter 9, i.e. Delaunay Triangulation, there is an exercise ...
The Limit Does Not Exist's user avatar
3 votes
1 answer
94 views

Collision between a bi-infinite linear sequence of 2D integer lattice points and any of a fixed set of such sequences

Given: a finite collection $V$ of bi-infinite linear sequences of two-dimensional integer lattice points, each sequence ${V_i}$ given by $\cdots,\vec{{V_i}_{-1}},\vec{{V_i}_0},\vec{{V_i}_1},\cdots$ ...
Szczepan Hołyszewski's user avatar
3 votes
0 answers
41 views

Periodic 4D Triangulations

I am looking for references and/or algorithms for generating 4-dimensional periodic triangulations on unit 4 lattices. That is, generating a space filling triangulation of the 4D integer lattice (Z^4) ...
user143907's user avatar
3 votes
0 answers
73 views

Approximation algorithm for minimal Covering of an orthogonal polyhedron

Covering an orthogonal polygon with rectangles is according to Culberson and Reckhow NP-complete, even for the case without holes. Franzblau shows an 2-approximation algorithm for simple polygons for ...
df21's user avatar
  • 63
3 votes
0 answers
51 views

Dynamically compute the union of polygons

Shorter version of my question: Is there any polygon union algorithm that allows me to change one of the polygons quickly? Longer version: Currently the major performance bottleneck I'm facing in one ...
Mu-Tsun Tsai's user avatar
3 votes
0 answers
121 views

Seemingly simple path finding problem, but graph with travelling salesman or shortest path does not work

I am looking for an algorithm to a problem that I encountered when working with 3D modeling: On a 3D triangle surface mesh, I have multiple lines, some of them are open, some are closed. The are on ...
Edgar's user avatar
  • 31
3 votes
0 answers
38 views

How to get the minimal enclosed polyhedra in a Line framework (points connectivity lists)?

Greetings all and thank you. I'm a Ph.D. candidate working on a force structure's 3D tessellation project and get stuck. I've simplified the system into a set of lines linked together which formed a ...
Simon Shi's user avatar
3 votes
0 answers
87 views

A simple algorithm to solve the MST Sensitivity Analysis problem in linear time when the MST is a path

The problem. Given an undirected, connected, edge-weighted graph $G=(V, E_G; w)$ and a minimum spanning tree (MST) $T=(V, E_T)$ of $G$, the MST sensitivity analysis problem asks to find, for each ...
Steven's user avatar
  • 29.4k
3 votes
0 answers
73 views

Number of permutations with satisfactory triangles

We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...
Jonathan Mcgee's user avatar
3 votes
0 answers
76 views

Calculating number of intersections of a horizontal line with line segments efficiently

I'm given an array $A = [a_1, a_2, ....a_n] $ using which I construct $n-1$ contiguous line segments by drawing a line from $(i,a_i)$ to $(i+1, a_{i+1})$. Now, I'm given $q$ queries in the form of $...
Kunal Gupta's user avatar
3 votes
0 answers
51 views

Distance from high dimensional convex hull to target point T

I have a set S of high dimensional points in Euclidean space, with convex hull H (not known); and some target point T in that space not in or on H. Rather than worry about calculating both H and the ...
jdowdell's user avatar
  • 131
3 votes
0 answers
80 views

Measuring the Union of Products of Intervals

Verbose Motivation for this Question Inspired by this paper about how the problem of counting unlabelled subtrees that are unique up to isomorphism is #P-complete, I was thinking about the problem ...
Zach Hunter's user avatar
3 votes
0 answers
282 views

Help understanding how to make a simple 3D minimum bounding sphere?

I need to develop a minimum bounding sphere. It'll only ever be in 3 dimensions, and the numbers of points are relatively small (500-5000 total). Performance is important however. I was looking for ...
Tyler Shellberg's user avatar
3 votes
0 answers
193 views

Overlay two Voronoi Diagrams and calculate membership and areas of intersecting polygons

I would like to generate a composite diagram of two Voronoi diagrams. I'm currently researching the cgal library for options, but I'm not sure if my precise application is covered. Basically, I have ...
Pedro Relich's user avatar
3 votes
0 answers
136 views

DCEL with dynamic graph

Is doubly-connected edge list a good data-structure for planar graph which vertices can be moved freely? I experienced DCEL as a very good structure when it comes to add/delete some vertex or edge. ...
JD.'s user avatar
  • 131
3 votes
0 answers
82 views

Self intersection in a simple polygon

Suppose I have a simple polygon whose vertices are $p_1,\ldots,p_n$ each $p_i \in \mathbb{R}^2$. Suppose now I pick two distincts vertices $p_i,p_j, i\neq j$ Is there some algorithm I can use to test ...
user8469759's user avatar

1
2 3 4 5 6