Questions algorithmic solutions of geometric problems.
2
votes
1answer
17 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
39 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 ...
5
votes
1answer
85 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
60 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$.
...
3
votes
1answer
52 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
$$
...
2
votes
0answers
45 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 ...
5
votes
1answer
58 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
116 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 ...
3
votes
1answer
50 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
80 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 ...
2
votes
0answers
103 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 ...
0
votes
1answer
70 views
naive convex hull algorithms
I already understood how the well-known algorithms like Graham, Quickhull etc. work, but i have difficulties in understanding 2 naive versions of convex hull algorithms:
...
4
votes
1answer
69 views
Data structures for general (non-tetrahedral) cell complexes
For 2D polygonal meshes, the QuadEdge and HalfEdge data structure representations are sufficient to store and enable efficient query of all topological and incidence information. Are there compact and ...
4
votes
3answers
191 views
Algorithm for getting the outer boundary of a large graph
I am trying to create an isochrone based on the OpenStreetMap data set. Everything works fine, I extracted data, processed it into a DAG, ran a Dijkstra algorithm over it. The result is a subset of ...
2
votes
1answer
72 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 ...
3
votes
1answer
77 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 ...
9
votes
0answers
167 views
How to pack polygons inside another polygon?
I have ordered a few leather sheets from which I would like to build juggling balls by sewing edges together. I'm using the Platonic solids for the shape of the balls.
I can scan the leather sheets ...
2
votes
0answers
22 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
62 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 ...
1
vote
1answer
123 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
154 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 ...
1
vote
1answer
115 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 ...
7
votes
1answer
197 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 ...
5
votes
1answer
146 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 ...
3
votes
1answer
130 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 ...
4
votes
0answers
162 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 ...
4
votes
1answer
119 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 ...
0
votes
0answers
54 views
2D Geometry manipulation papers/search keywords
I'm searching papers about the history and evolution of 2D geometry manipulation and engines, but I can't find what I'm looking for. Can someone help me with some recommended papers or recommended ...
6
votes
2answers
167 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, ...
6
votes
1answer
342 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 ...
4
votes
1answer
635 views
Constructing of Double Connected Edge List (DCEL)
For a given planar graph $G(V,E)$ embedded in the plane, defined by list of segments $E= \left \{ e_1,...,e_m \right \} $, each segment $e_i$ is represented by its endpoints $\left \{ L_i,R_i ...
7
votes
4answers
404 views
Shortest distance between a point in A and a point in B
Given two sets $A$ and $B$ each containing $n$ disjoint points
in the plane, compute the shortest distance between a point in $A$ and a point in $B$, i.e., $\min \space \{\mbox{ } \text{dist}(p, ...
10
votes
1answer
336 views
Brute force Delaunay triangulation algorithm complexity
In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm uses the ...
1
vote
2answers
156 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
169 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
1answer
224 views
Testing Polygon for Monotonicity with respect to any arbitrary line
Definition: monotone polygon - a polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice.
I am wondering if ...
6
votes
2answers
116 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$ ...
6
votes
1answer
138 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:
...
12
votes
1answer
181 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. ...
6
votes
0answers
340 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 ...
6
votes
2answers
163 views
If a point is a vertex of convex hull
The exercise is
Given a set of point $S$ and a point $p$. Decide in $O(n)$ time if $p$ is a vertex of convex polygon formed from points of $S$.
The problem is I am a little bit confused with ...
8
votes
2answers
211 views
Maximum Enclosing Circle of a Given Radius
I try to find an approach to the following problem:
Given the set of point $S$ and radius $r$, find the center point of circle, such that the circle contains the maximum number of points from the ...
14
votes
3answers
331 views
Line separates two sets of points
If there is a way to identify if two sets of points can be separated by a line?
We have two sets of points $A$ and $B$ if there is a line that separates $A$ and $B$ such that all points of $A$ and ...
6
votes
2answers
107 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.
...
6
votes
1answer
113 views
Testing Polygon for Monotonicity
It's well known that Monotone polygon plays a crucial role in Polygon triangulation.
Definiton: monotone polygon - a polygon $P$ in the plane is called monotone with respect to a straight line ...
13
votes
2answers
219 views
Runtime of the optimal greedy $2$-approximation algorithm for the $k$-clustering problem
We are given a set 2-dimensional points $|P| = n$ and an integer $k$. We must find a collection of $k$ circles that enclose all the $n$ points such that the radius of the largest circle is as large as ...
7
votes
2answers
444 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) ...
9
votes
2answers
1k views
Circle Intersection with Sweep Line Algorithm
Unfortunately I am still not so strong in understanding Sweep Line Algorithm. All papers and textbooks on the topic are already read, however understanding is still far away. Just in order to make it ...
9
votes
1answer
141 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 ...
9
votes
1answer
175 views
Distribute objects in a cube so that they have maximum distance between each other
I'm trying to use a color camera to track multiple objects in space. Each object will have a different color and in order to be able to distinguish well between each objects I'm trying to make sure ...
