Questions tagged [computational-geometry]

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

Filter by
Sorted by
Tagged with
5
votes
1answer
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 ...
3
votes
0answers
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 ...
5
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
0answers
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 ...
4
votes
1answer
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 ...
3
votes
0answers
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 ...
1
vote
3answers
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 ...
7
votes
1answer
10k views

Checking Feasibility of Linear Program in Polynomial Time

Given a linear system of the form: $$\begin{array}{c} x_r = a \quad x_j = b \\ c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\ x_1+x_2 + x_3 + \ldots + x_n = k\\ 0 \le a,b,x_1,x_2,x_3...x_n \le 1\\ k \ge 0 \...
6
votes
1answer
319 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 ...
0
votes
0answers
297 views

3D wireframe algorithm

We need to convert wireframe representations of 3D objects into a representation consisting of 6 orthogonal views each containing nested (non intersecting) closed contours, each having a Z (depth/...
1
vote
2answers
336 views

Pairwise comparisons with confidence

There is a lot of information available on the subject of Pairwise Comparisons but I haven't found any guidance on how to optimize pair measurements that have confidence values attached to them. ...
7
votes
1answer
1k views

Convex polygon formulation

We have a sorted list of side lengths that can be used to form a polygon. There are $n$ such values ($n \le 1000$). Now we need to find if we can use any 10 of these values to form a non-degenerate ...
4
votes
2answers
1k views

Finding least number of line segments with length $L$ that cover $N$ points

The problem is defined as: Given $N$ points on an infinite line, find the least number of line segments of length $L$ that cover all points (including endpoints) after changing one point. That ...
1
vote
1answer
224 views

Efficient algorithms for finding a region in $\mathbf R^2$

This question is an extension of a previous question I've asked. Consider the rectangle $a<x<b , c<y<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 (...
2
votes
2answers
249 views

Complexity of an algorithm for bounding a region in 2D

First I apologize if the title is unclear, but I didn't find anything better. I'm solving a differential equation that has two parameters , here denoted by points of a plane.These parameters are real ...
3
votes
1answer
198 views

Randomized convex hull

I've been recently studying Monte-Carlo and other randomized methods for a lot of applications, and one that popped into my mind was making an (approximate) convex hull by examining random points, and ...
0
votes
1answer
135 views

Bounding rectangle of a line

[Input]: the begin and end points of an arbitrary line (small red points) and the line width (green line) [Example]: begin=(20,20), end=(100,50), width=5 [Output]: The set of pixels (not the total ...
7
votes
1answer
2k views

Algorithm to find a line that divides the number of points equally

I have recently been asked in an interview to devise an algorithm that divides a set of points in a coordinate system so that half of the points lie on one side of the line, and the rest on the other ...
2
votes
1answer
453 views

Euclidean Steiner Tree Question in Approximation Algorithms

Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$. ...
4
votes
1answer
186 views

How come the Bernstein operator creates a polynomial of the same degree as its input function?

I read that the Bernstein operator $$ \mathfrak{B}_f(t) = \sum_{i=0}^n f\left(\frac{i}{n}\right) \; B^n_i(t) $$ applied to a polynomial $f(x)$ of degree $m \leq n$ with the Bernstein polynomial $$ ...
6
votes
0answers
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 (...
8
votes
1answer
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 ...
4
votes
1answer
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 ...
6
votes
1answer
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?
3
votes
1answer
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-...
3
votes
0answers
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 ...
2
votes
1answer
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 ...
10
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
5
votes
2answers
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 ...
6
votes
1answer
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: ...
7
votes
1answer
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 ...
7
votes
1answer
3k views

Lower bound for Convex hull

By making use of the fact that sorting $n$ numbers requires $\Omega(n \log n)$ steps for any optimal algorithm (which uses 'comparison' for sorting), how can I prove that finding the convex-hull of $...
9
votes
2answers
7k views

Algorithms for two and three dimensional Knapsack

I know that the 2D and 3D Knapsack problems are NPC, but is there any way to solve them in reasonable time if the instances are not very complicated? Would dynamic programming work? By 2D (3D) ...
2
votes
1answer
243 views

Sensor Cover Problem

We are given an interval $I$ and several points $p_1,p_2,...,p_n$. We are also given a set of sensors. Each sensor can be represented by an interval on the same line, which means all points lie within ...
5
votes
0answers
732 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 ...
14
votes
1answer
415 views

Coverage problem (transmitter and receiver)

I try to solve the following coverage problem. There are $n$ transmitters with coverage area of 1km and $n$ receivers. Decide in $O(n\log n)$ that all receivers are covered by any transmitter. All ...
7
votes
2answers
151 views

Connection between castability and convexity

I am wondering if there are any connection between convex polygon and castable object? What can we say about castability of the object if we know that the object is convex polygon and vice versa. Let'...
4
votes
1answer
589 views

Finding a minimal containing rectangle from a given set of rectangles

The problem is as follows: Given a finite set of rectangles ($S\subset\mathbb{R}\times\mathbb{R}$), build a data structure that will support the following operations: Check, receives a rectangle $r\...
5
votes
1answer
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 ...
8
votes
2answers
268 views

Maximum number of points that two paths can reach

Suppose we are given a list of $n$ points, whose $x$ and $y$ coordinates are all non-negative. Suppose also that there are no duplicate points. We can only go from point $(x_i, y_i)$ to point $(x_j, ...
7
votes
1answer
3k views

If any 3 points are collinear

Given a set $S$ of points $p_1,..,p_2$ give the most efficient algorithm for determining if any 3 points of the set are collinear. The problem is I started with general definition but I cannot ...
6
votes
2answers
222 views

Finding the point nearest to the x-axis over some segment

I have problem with solving the following exercise Given the set $P$ on $n$ points in two dimensions, build in time $O(n\log n)$ a data structure of $P$ such that given a horizontal segment $s$ ...
2
votes
2answers
1k views

"Flow layouts" inside a GUI -- how do I come up with a good algorithm?

I was trying to write some simple code for a "flow layout" manager and what I came up with initially was something like the following (semi-pseudocode): ...
2
votes
1answer
469 views

Point Location Problem in Polygon in Repetitive Mode for a Simple Polygon

I consider Point Location Problem in Polygon in repetitive mode in the case of simple polygon. In computational geometry,Point Location Problem in Polygon problem asks whether a given point in the ...
8
votes
0answers
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....
6
votes
1answer
118 views

How to score a given arrangement of windows on a screen to produce good layouts

(this is related to my other question, see here) I would like to write a function that scores a given arrangement of windows on a screen. The purpose of this function is to determine whether a ...