A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [computational-geometry]

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

607 questions
Filter by
Sorted by
Tagged with
35 views

### Robust two lines/segments intersection point in 2D

Given two line segments the problem is to find an intersection point of corresponding lines (assuming that they are not parallel or coincide). There is a Wikipedia article which gives us exact ...
69 views

### Separating the snakes

In a two-dimensional grid, there are $n$ "snakes" (sets of contiguous grid-blocks). The snakes do not touch each other. The goal is to cut the grid into $n$ rectangles using $n-1$ "fences" (horizontal ...
16 views

### Status on Naoki Katoh's “Rectangle Wiring Problem”?

I have found this interesting problem in graph theory and geometry which is allegedly an open problem but latest status seems to be from 01/25/02. I can't see to find any more information about it, ...
121 views

### Find vertices of a convex polytope, defined by intersecting half-spaces

I am looking for a algorithm that returns the vertices of a polytope if provided with the set of intersecting half-spaces that define it. In my special case the polytope is constructed by the ...
42 views

### Interpolation: How to generate 3D objects from 2D cross-sections?

Consider a sphere sitting on an $xy$-plane, and take 2D slices parallel to the $xy$-plane at various heights of z. Suppose we take 10 slices, evenly spaced along the $z$-axis, and now have 10 images ...
42 views

### Convert a polygon mesh into a b-spline surface

$\textbf{Problem:}$ Getting a $\textit{polygon-mesh}$ as input, I have to construct a surface that looks exactly to the given input. My task is to generate a $\textit{b-spline}$ surface that exactly ...
51 views

### Triangulation of disjoint line segments

Given a set of disjoint line segments in the plane, prove (or disprove) that you can always join the line segments to make a near-triangulation where the vertices are the endpoints of the segments, ...
44 views

### Joining line segments to make tree

Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and ...
38 views

### Prove vertices of polygon are endpoints of disjoint line segments

If we are given a set of disjoint line segments in the plane, can we prove (or disprove) that we can always join the line segments to make a simple polygon where the vertices of the polygon are the ...
67 views

### Near Triangulation Planar Graph

This is the problem I am dealing with: Given a set P of n points in general position, let a graph G be defined as follows: The vertex set is P. Two vertices, a and b, are joined by an edge provided ...
69 views

### Voronoi Diagram Drawing Variations and Charateristics

I am learning about Voronoi diagrams and I have seen that the Voronoi diagram of a set of points is drawn with straight line segments and rays. Similarly how can we draw the Voronoi diagram for the ...
95 views

### Voronoi Cell and Voronoi Diagram

Consider a set R of n red points and B of n blue points in the plane. Let x∈R and y∈B be the shortest edge xy. Let P = R ∪ B. Let Vor(P) be the Voronoi diagram of P. Let V(x) be the Voronoi cell of x ...
102 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 ...
55 views

### Dynamic length of union of segments (1d Klee's measure problem)

Finding the length of union of segments (1-dimensional Klee's measure problem) is a well-known algorithmic problem. Given a set of $n$ intervals on the real line, the task is to find the length of ...
36 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 ...
40 views

### Upper (or lower) envelope of some linear functions

Given some single variable linear functions $y_1=m_1x+b_1$, $y_2=m_2x+b_2$, $\ldots$, $y_n=m_nx+b_n$, the upper envelope is the function $f(x)= \max \{y_1, \ldots, y_n\}$. We know that this function ...
383 views

### How to devise an algorithm to generate a random but valid train track layout?

I am wondering if I have quantity C of curved tracks and quantity S of straight tracks, how I could devise an algorithm, (computer assisted or not), to design a "random" layout using all of those ...
10 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 (...
35 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 ...
23 views

### Is there a way to perform calculations of Mandelbrot set using only integer numbers?

I would like to create program in JavaScript (JS) which draws Mandelbrot set with arbitrary precision (zoom). In JS there is build in integer type BigInt which support simple operations like +,*,/,...
19 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 ...
12 views

### Algorithm for animating/morphing convex polygon diagrams

I am trying to find an algorithm to smoothly morph a (given) diagram made of convex polygons into another (given) diagram of the same type. The target diagram is usually generated from the source, ...
51 views

### O(n) external intersection points?

I have a doubt. For a given n (axis-parallel) squares in a plane, where there are Ω(n²) intersection points between the edges of the square, is it possible to have O(n) external intersection points? (...
58 views

### Data structure to report all axis aligned bounding boxes intersecting an axis aligned query line

I would like to build a Data structure that uses subquadratic space to quickly report a set of AABBs (axis aligned bounding boxes) in 3 dimensional space when it intersects a query line? I am only ...
48 views

### Given a set of (x,y) coordinates, give the set of edges to draw a simple polygon

Let's say I give you the following array of points: (1,1) (1,3), (2,2), (4,1), (4,3) My (terrible) mspaint drawing of the shape that would be created by these looks like this: How, given an ...
31 views

### Given a DCEL, how do you identify the unbounded face

I have constructed a DCEL using the procedure described in How do I construct a doubly connected edge list given a set of line segments?. This correctly identifies all faces, however I'm struggling ...
20 views

### Is there a way to *round* a nearby point into the feasible set?

Let $P \subset \mathbb R^d$ be a polytope with interior given by $F$-many linear inequalities. Suppose we have a convex problem with feasible set $P$. For example computing the Euclidean projection of ...
33 views

### How Expensive is Projecting onto a Polytope?

I have a problem where our action set is a polytope $\mathcal P\subset \mathbb R^d$ and an algorithm that involves projecting onto the action set. For example it says to select the Euclidean ...
1k views

### How can I determine if two vertices on a polygon are consecutive?

Suppose I have a set of points that construct a convex polygon in the Cartesian plane with the points as its vertices. I randomly choose two vertices and want to know if they are consecutive vertices ...
22 views

### RGBD alignment without explicit transformation between RGB and depth

I have a set of RGB-D scans of the same scene, corresponding camera poses, intrinsics and extrinsics for both color and depth cameras. RGB's resolution is 1290x960, depth's is 640x480. Depth is ...
29 views

### What is the name of this problem (the dual of the asymmetric k-center problem)

I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse. In this ...
22 views

### How to find a path in maze with navigator physical size constraints?

Assuming a 2D maze, how would one go about solving it for rigid 2D object moving through it? Additional specification: The object shape - it is a single entity, not a swarm/fleet. A shape of ...
40 views

### Efficient data structure for matching 3D lines

I'd like to Store a set of many infinite undirected 3D lines. Make lookups against this set - i.e. given an arbitrary line, ask "Does the set contain a line coincident with this one?" The incidence-...
58 views

### Hexagon packing algorithm

I'm trying to pack hexagons, within bigger hexagons, as shown here: For this example, I have 5 "children" to put in my "father" hexagon. Each time I've got too many children, I would like to reduce ...
168 views

### Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time

A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the ...
36 views

### Efficient algorithm to filter off points from a point cloud

I have a master point cloud, which essentially just a list of points with {x,y} coordinates. The point cloud is HUGE ( like, it can contain more than 1 million ...
52 views

### Perpendicular vectors out of a set

I stumbled on this problem and I wanna know if there is a better solution. There are $n$ 3d vectors with $x$, $y$, and $z$ components and I wanna find all pairs of perpendicular vectors in this set. ...
16 views

### Segment 3d mesh into multiple 3d meshes with equal size

Given a 3d mesh, for example the stanford bunny, how can I segment the mesh in a way that each segment has a roughly equal size between them? Assuming the target number of segments is given as an ...
77 views

### High-dimensional geometry and P vs. NP

Background: Recently, I obtained the following equivalent problem to SAT. We are given as input a CNF formula with $n$ variables and $m$ clauses. Suppose we have an $n$-dimensional hyper-cube centered ...
70 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 ...
29 views

### Maximum and Minimum distance from query point within bounding box

I'm reading an article regarding approximating sums using KD-trees (similar to FMM). As part of the effort I'm trying to make sense of this article , which is cited. I'm having trouble understanding ...
51 views

### Finding the closest visible vertex among line segments

Given a set $S$ of line segments (possibly sharing endpoints) and a query point $q$, how fast can we find the closest visible endpoint from $q$? If $p$ is the closest visible endpoint to $q$, then, in ...
85 views

### Intersection of O(n) expanding circles with line from the origin

I am interested resolving a programming challenge problem, but I'm struggling obtaining an efficient solution. Consider yourself as a point located on the origin $(0,0)$ of an infinite two-...
20 views

### Configuration space for multi robot system

I have a problem that I think can be casted in the following way. Suppose I have a simple closed polygon $\mathcal{P}$ and $n$ squares (bounding boxes) $\mathcal{B}_1, \ldots, \mathcal{B}_n$, you can ...
30 views

### Non intersecting paths of graphs with obstacle number one

There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
16 views

### Review of fast 2D strip packing algorithms?

It seems to me that strip/bin packing algorithms must balance between two criterion: 1) how long it takes to perform the packing 2) how area-efficient the packing is (i.e. how minimal wasted area is)...
142 views

### Given n sets of points in the plane find the shortest path which passes from exactly one point from each set

I am trying to find an algorithm for this. You can imagine each set $(S_1, S_2, \ldots, S_n)$ as points with different colour. Also it isn't necessarily $|S_1|=|S_2|=\cdots=|S_n|$. For $n=1$ we ...
17 views

### How to identify a continuous shape and break it into minimum number of rectangles?

The input in this case is going to be coordinates in 2D of the vertices of the shape. There will be no curves, but the shape can have holes. The algorithm or program needs to identify the continuous ...