Questions tagged [computational-geometry]

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

756 questions
Filter by
Sorted by
Tagged with
224 views

Complexity of finding a spanning tree that minimizes the maximum interference

Given $n$ nodes in the plane, connect the nodes by a spanning tree. For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning ...
323 views

Suggestions for alternative 3D space partition tessellation, different from Voronoi and Delaunay

I have a system of mono-disperse spheres inside a cubic box. I am studying the volume distribution inside the sample, after tessellating it with either Voronoi and Delaunay tessellations. I am ...
886 views

Comparing sets of vectors

If $u,v \in \mathbb{R}^d$ are two $d$-dimensional vectors, say that $u\le v$ if $u_i \le v_i$ for all $i=1,\dots,d$. In other words, comparisons on vectors will be pointwise. Let $S,T$ be two ...
2k views

How does sorting come into play with convex hull?

I am investigating a convex hull algorithm that involves sorting. In fact, its running time is limited by sorting, so it is $O(n \log n)$, where $n$ is the number of points on the plane. That ...
612 views

Motion planning using second order Bézier curves

I'm trying to find an algorithm for a motion planning problem. I have $N$ points, $P_1$ to $P_N$, in $k$-dimensional cartesian space, defining $N-1$ segments. The problem is about constructing the ...
1k views

Box and triangle intersection

I am looking for geometry algorithm. I have an axis-aligned box $B$ and a triangle $T$ in 3D space. I want to compute an axis-aligned bounding box of their intersection. Both $B$ and $T$ are convex ...
177 views

Drawing Zonotopes from an Adjacency Matrix

I'm conflicted whether to post this here or in either math.stackexchange or mathematica.stackexchange. Define a "simple zonotope" to be a regular $2n$-gon which is tiled by the following rule: all ...
819 views

Finding the shortest path in a n-dimensional grid

I have an $n$-dimensional grid space with two points on it defined by ordered pairs. I want to find the shortest path between the two points, but I can only increase one number in the ordered pair at ...
10k views

585 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 (...
476 views

Circles covering a rectangular, how to verify it?

This may be basic to some of you, but excuse my inexperience with comp. geometry: Given a set of $n$ circles with centers $(x_i, y_i)$ for $1 \leq i \leq n$ and each having radii $r$. Also given a ...
2k views

An algorithm for fitting a rectangle inside a polygon

I have a kind of cutting problem. There is an irregular polygon that doesn't have any holes and a list of standard sized of rectangular tiles and their values. I want an efficient algorithm to find ...
2k views

Find the point with minimum max distance to any point in a set

Say I have a set of points on a 2d plane, how do I find the point(s) where the maximum euclidian distance to any of the points in the set is minimized?
124 views

Choose a "middle" point from a set

I read a post which talks about pretty much the same problem. But here I simplify the problem hoping that a concrete proof can be offered. There is a set $A$ which contains some discrete points (one-...
1k views

Why does Graham Scan not extend to three dimensions?

The Graham scan algorithm computes the convex hull of a finite sets of points. It works only in the plane but is also fast (time $O(n \log n)$). An old exam question asks, why does the algorithm not ...
239 views

Validating a sequence of points as a convex hull

I'm familiar with the classical convex hull calculation algorithms. The lower bound for computing the CH of a set of points $P$ is $n\log(n)$. However, what if I'm given a sequence of points and ...
2k views

How to find contour lines for Appel's Hidden Line Removal Algorithm

For fun I am trying to make a wire-frame viewer for the DCPU-16. I understand how do do everything except how to hide the lines that are hidden in the wire frame. All of the questions here on SO all ...
171 views

Maximum feasible subsystem problem (MaxFS) in 2 variables

Topic: The maximum feasible subsystem problem, which is generally NP-hard [1]. Question: Are there special algorithms in case of only 2 variables (2D linear constraints)? The problem seems to be a ...
137 views

Voronoi diagram with given number of vertices and sites

I want to draw a Voronoi diagram with 9 sites and with no vertex, 1 vertex, 4 vertices, and 7 vertices. How do I approach this question. The one with no vertex is easy, it can be done by ...
1k views

Minimum weight triangulation

I'm just curious about the pseudocode (or real source code, doesn't matter) of the recursive version of this algorithm. In almost every book chapter/paper when describing this topic, they mention that ...
192 views

Is the following NP-complete?

I have encountered the following problem. We have $N$ points in discrete coordinates,distributed through a plane with vertical axis $[1..Y]$ and horizontal axis $[1..X]$. We can perform the action of ...
536 views

Algorithm to minimize distance variance between 2D coordinates

I've been looking around for an algorithm that would optimize the distance between 2 list of coordinates and choose which coordinate should go together. Say I have List 1: ...
2k views

Line smoothing algorithm that perserve data uniformity

Intro: I'm working with huge data set that i need to plot in browser, and since there may be up to 1M points my idea was to create different representations for different zoom levels lets say i have ...
3k views

2k views

Polygons generated by a set of segments

Given a set of segments, I would like to compute the set of closed polygons inside the convex hull of the set of the end of those segments. The vertices of the polygons are the intersections of the ...