Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

-2
votes
0answers
21 views

Villagers move to a safe location in a catastrophe [on hold]

Assume there are n villages on a straight line. Each village has a population p located at a distance d from a base location (0,0). During a catastrophe, all villagers are requested to move to a ...
0
votes
0answers
12 views

Algorithm for projection of polytope

Let a convex bounded polytope be given by an intersection of half planes: $Ax \leq b$. Let $z=Cx$ be a vector (in my case $z$ is 2-dimensional, while $x$ has a higher dimension). How can I compute ...
7
votes
1answer
112 views

Find the central point in a metric-space point set, in less than $O(n^2)$?

I have a set of $n$ points which are defined in a metric space – so I can measure a 'distance' between points but nothing else. I want to find the most central point within this set, which I ...
3
votes
1answer
71 views

Covering a polygon with n circular rings

Question 1: Why we can/can't solve the following problem using a geometric constraint solver? Question 2: Is there any algorithm to solve this problem? Question 3: Can we reduce this problem into some ...
2
votes
1answer
25 views

What are algorithms for computing contours from given edges?

Let's say I have a set of edges which makes the contour, however there are too many of them and some are too long. I have to remove edges, and shorten them to make contour. I cannot add new edges! I ...
1
vote
1answer
20 views

Getting the essential from the fundamental matrix

Is it possible to get E from F? I suppose that can't work, because then I could calculate the the extrinsic (and maybe also intrinsic?) parameters of the cameras without a calibration object of known ...
2
votes
1answer
15 views

Fundamental and essential matrices, value of intrinsic parameters

I observe a scene with two cameras, c1 and c2, that produce two images i1 and i2, respectively. What I ultimately want to do is to use information of image i1 and image2 simultaneously, e.g., for ...
0
votes
1answer
35 views

Bringing images into alignment

I observe a scene with two cameras, c1 and c2, that produce two images i1 and i2, respectively. What I now want is to bring i1 and i2 into alignment, that is I want to know where pixel (x,y) in i1 is ...
1
vote
1answer
42 views

Merging of two convex polygon chains in O(log n)

Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the ...
2
votes
2answers
82 views

Encircling randomly distributed points

I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly p points. We also (randomly) place c circle centres. I'm trying to find an algorithm that will allow ...
-1
votes
1answer
127 views

Computing the number of squares which are intersected by a line internally

There's a line from (x1,y1) to (x2,y2) in a grid of squares of unit length. Write a program to compute the number of squares which are intersected by the line internally, i.e squares which are only ...
0
votes
2answers
25 views

“Practical” bounding box?

For the sake of simplicity, lets say I have a bunch of 2d points, each have X and Y. The points are distributed somewhat randomly but not completely, they will be biased to be closer to the world ...
1
vote
0answers
23 views

Boundary tracing of simple closed curves? [closed]

I have some heavy calculations that essentially takes a point in the plane as input and gives an integer as output. Points in the same region gives the same integer (think about the regions as pieces ...
1
vote
1answer
50 views

Divide and Conquer 3D Convex Hull [closed]

http://cs.jhu.edu/~misha/Spring14/Preparata77.pdf This is a divide and conquer algorithm for computing the convex hull in 3 dimensions. I am having trouble understanding the merge step, which is ...
5
votes
0answers
54 views

Uniform Sampling on Intersection of Faces of Simplices

I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints $$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq ...
5
votes
1answer
51 views

Delaunay Triangulation on Convex Polytopes — Uniform Sampling

My goal is to uniformly sample from a convex polytope. I know that for the simpler case, where I have to uniformly sample from a simplex, I can use Bayesian Bootstrap, discussed in these posts: ...
0
votes
0answers
13 views

Generating path vectors from point-to-point data

I have a list of point-to-point $(x,y)$ positions representing a path. I would like to convert these points to a list of vectors consisting of straight segments $\{L\}$ and turn vectors $\{r, ...
0
votes
0answers
19 views

Is there a good model of computation for real numbers? [duplicate]

/!\ I am not speaking about int or float, my question is about model of computation used to design and describe algorithms. The integer numbers case Many algorithms use integers and their ...
2
votes
1answer
54 views

Turning a simple polygon with holes into exterior-bounded only

I am converting cartographic objects, which have an exterior boundary (simple polygon) and zero or more interior boundaries (also simple), into a less sophisticated format that specifies exterior ...
2
votes
1answer
70 views

Fast algorithm for interpolating data from polar coordinates to cartesian coordinates

I have a set of solution nodes generated over a polar grid. I would like to convert / interpolate these solution nodes onto a Cartesian grid: That is, using the image above, for each node in the ...
0
votes
1answer
43 views

Most Efficient Method To Determine Triangle Fill Values Based On Corner Values

I have a triangle and the value of the pixel intensity at each of the three corners of the triangle. I want to interpolate to find interpolated pixel intensities for a set of points inside the ...
2
votes
1answer
35 views

Algorithms that are using John's ellipsoid

The Lowner–John ellipsoid is a minimum volume enclosing ellipsoid of some convex body $K$. This ellipsoid is unique (as is the maximum volume ellipsoid contained in $K$). I'm looking for ...
1
vote
0answers
8 views

Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm

Roughly, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain. The algorithm specifies splitting the edges at their ...
3
votes
0answers
39 views

Finding the distance to the nearest neighbor for each point in a set of points in $R^n$

I have a list of points in $R^n$, and for each point I want to find the Euclidean distance to the nearest other point in the list. I don't need to know the coordinates of the nearest neighbor; I only ...
3
votes
1answer
26 views

Creating a 2D map of objects given a sparse matrix of pairwise distances

I have a set of points on the two-dimensional plane, but their locations are not given to me. I am given the distance between some pairs of the points. However, I only know these differences for ...
0
votes
2answers
77 views

How to expand 2D graphic and functions to 3D?

So I have a program that enables the user to draw 2D-objects. To rotate them, to move them, and so on, all in 2D. I want to expand the 2D objects and functions to 3D which I don't expect to be too ...
1
vote
0answers
27 views

What is the intuition behind the “edit sensitive parsing” tree?

If I understand right then ESP tree is defined as : given any string $x$ of finite length over an alphabet one can construct "an" ESP tree corresponding to it say $T_x$ such that each leaf of the tree ...
3
votes
1answer
50 views

Minimum Length Hamiltonian Path Pair in O(n^2) or better

A friend and I have been discussing turning a $O(n^2)$ graph problem's algorithm into $O(n\log n)$, or at least less than $O(n^2)$. And no - this is not a homework question. We've narrowed it down to ...
4
votes
0answers
26 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 ...
3
votes
1answer
39 views

Lower bound for maxima on 2D plane

Given $n$ points $(x_1, y_1), \ldots, (x_n, y_n)$ on a 2-dimensional plane. A point $(x_1, y_1)$ dominates $(x_2, y_2)$ if $x_1 > x_2 \land y_1 > y_2$. A point is called a maxima if no ...
11
votes
1answer
612 views

What is the use of finding minimum number of straight lines to cover a set of points?

There is that popular problem [1] [2] in the computer science that is finding minimum number of straight lines that covers a given set of points in 2D. Even though I have scanned many papers, none of ...
3
votes
0answers
41 views

Complexity of clustering lattice points

[Note] I have completely rewrited the question after Yuval's comments. I hope it makes more sense now! $\newcommand\ZZ{\mathbb Z}$$\newcommand\dist{\operatorname{dist}}$Consider the $d$-dimensional ...
3
votes
1answer
48 views

What are some interesting applications of the skyline problem?

You are given a set of $n$ rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each ...
2
votes
1answer
68 views

Weighted closest-pair-of-points problem

I want to solve the following optimisation problem (an approximation or heuristic would be helpful as well). I have two sets of points in the plane: $P=\left\{ p_{1},p_{2},\dots,p_{N}\right\} $ and ...
5
votes
1answer
121 views

Reduction from Vertex Cover to Polygon Cover

Polygon Cover: Input: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$. Output: True if and only if there exists a subset in $S$ of at most $k$ ...
1
vote
0answers
39 views

How do you find the union of the the unit squares contained in a polygon?

The Problem: Suppose you have a simple polygon (edges don't cross). Find the union of of all 1x1 squares that fit in the polygon. To be clear, I am asking for the union of all points that are in ...
1
vote
1answer
31 views

Finding stabbing numbers for lines for a set of segments in the plane

So we have a lot of line queries in the plane, and for each line query we want to know the number of segments that intersect that line (are stabbed by the line) for a given set of segments in the ...
0
votes
2answers
45 views

Given a pair of coordinates $(x,y)$ in 2D, find the points inside the circle $C((x,y),R)$

Suppose that there are a set of $n$ points $P = \{(x_1,y_1), \dots, (x_n,y_n)\}$ in 2D. Given two coordinates $(a,b)$ and a number $r \in \mathbb{R}$, is there an algorithm with $O(|Q| + \log n)$ ...
4
votes
1answer
85 views

How to find a subset of potentially maximal vectors (of numbers) in a set of vectors

I have a set S (so no duplicates) of d-dimensional vectors of non-negative real numbers (or if you would prefer, floats). I say a vector u "covers" a vector v if, in every dimension 1..d, u[i] >= ...
2
votes
0answers
21 views

Fast search of local positive quadruples on the sphere

[redirected from math.stackexchange.com] Let $U = \{u_{1}, u_{2}, \ldots, u_{n}\} \subset \mathbb{R}^{3}$ be the finite set of points on the unit sphere in $\mathbb{R}^{3}$: $||u_{i}||_{2} = 1$ ...
0
votes
0answers
79 views

What data structure would help find nearby coordinates quickly?

I need to write a program that does the following: Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places Store them in a data structure once Provide ...
1
vote
2answers
249 views

Determine whether a point lies in a convex hull of points in O(logn)

I've researched several algorithms for determining whether a point lies in a convex hull, but I can't seem to find any algorithm which can do the trick in O(log n) time, nor can I come up with one ...
1
vote
0answers
28 views

Modify one element and find out which surounding elements are affected

I want to know if there is an algorithm which does the following: Imagine you have a point cloud and the points affect each other but the action from each point to an other is only valid in some ...
0
votes
0answers
61 views

Data Structure implementation to store Sweep Line Status in Sweep Line Algorithms

I have been trying to implement the data structure for storing the sweep line status in sweep line algorithms (eg. Bentley-Ottmann for line segment intersection) and finding it difficult to implement ...
2
votes
0answers
60 views

Data Structure for storing the Sweep Line Status in Sweep Line Algorithms

I have been looking into the sweep line algorithms of finding intersection of line segments and polygon partitioning using monotone polygons. The algorithms require a dynamically balanced binary tree ...
2
votes
1answer
244 views

Finding the Best Fitting Plane Given a Set of 3D Points

Suppose that we have $n$ points in 3D. I want to find a plane $ax + by + cz + d$ such that sum of all the orthogonal distances to the plane is minimum. I read this article. However, I need an ...
0
votes
0answers
33 views

Polygon offset from two closed curves

Let $P$ be a simple polygon, let $\delta$ the minimum distance from any vertex $v$ of $P$ to any edge of $P$ that is not incident to $v$, and let $0 <\epsilon<\delta/2$. How can I prove that the ...
2
votes
1answer
52 views

Good data structure for finding all points in one set a distance from each point in another set

Let $X$ and $Y$ be two sets of points in $\mathbb{R}^3$. Assume that the cardinality of $Y$ is larger (much larger if you want) than $X$. For each $x_i \in X$, I need to find all $y \in Y$ such that ...
2
votes
1answer
63 views

Constructing non intersecting segments from distinct sets of points

Given 2 sets of points in the plane, $A$ and $B$, each of size $n$, I need to construct n line segments of the form ($a$–$b$) ($a$ in $A$, $b$ in $B$) such that none of them intersect. The ...
1
vote
0answers
29 views

n-point hull of a set of points

I ran into the following, deceptively simple problem, and I was wondering if there is a well-known algorithmic solution to it: Given a set of points $S$ in $\mathbb{R}^d$ (or $\mathbb{R}^2$, for ...