Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

2
votes
0answers
17 views

Generating a random, dense set of points subject to proximity restrictions?

I recently read a paper about hyperuniform distributions, which mentioned that one way to generate a rectangle filled with hyperuniformly-distributed points is the following: Choose a uniformly-...
0
votes
0answers
20 views

Percent of rectangle intersected by circle

I'm searching for an algorithm which, given specifications of a circle and a rectangle, returns the percentage of the rectangle intersected by the circle. In other words, given $(x,y)$ (the center of ...
0
votes
0answers
52 views

Understanding Chazelle's bin packing algorithm

I'm having trouble understanding Chazelle's algorithm ,which is discussed in this paper The bottom-left bin-packing heuristic: an efficient implementation by B. Chazelle (1983), especially in ...
4
votes
1answer
47 views

Finding a minimal width strip which encloses a set of points in the plane

Problem: Consider a set of $n$ points in the plane, how could we find a strip of minimal vertical distance that contains all points? Definitions: A strip is defined by two parallel lines and the ...
3
votes
2answers
79 views

Generate random point inside a polyhedron

I would like to know if there are known algorithms for generating a random point(say following a probability distribution P) inside an arbitrary polyhedron(possibly non-convex and may contain holes)? ...
0
votes
0answers
17 views

k-Closest pairs in Delaunay triangulation

Assume there is a set of points $S$ in $\mathbb{R^2}$. In this set of points there is a pair of points which are the nearest neighbors, the second-nearest neighbors and the third-nearest neighbors. I ...
3
votes
1answer
44 views

Showing that all vertex degrees in MSTs of Euclidian graphs are in O(1)

There is a finite set of points $S$ in the plane with $ |S| = n$. MST is the minimal spanning tree of S. "Minimal" here refers to the Euclidean distance between the points of $S$, so the MST is the ...
1
vote
1answer
30 views

Hyperplane through origin which goes through most number of points

Given $M$ points in $\mathbb{R}^{N}$ (where $M$ is larger than $N$), I was wondering if there is an algorithm to find a $N-1$-dimensional hyperplane which goes through the origin and also intersects ...
3
votes
1answer
34 views

Algorithm to enclose a 2D-gridbased-room efficient

I have the problem that I have a grid-based room which has 1 or more exits and I want to "secure" the room with minimal effort. Here a little Example: In this example black squares are not ...
0
votes
0answers
21 views

Identify large (convex) polygons

I have a point cloud that has several connections. What I want to identify are the largest (by area) irregular (convex) polygons. I put convex in brackets as it is not fully necessary (like in the red ...
-3
votes
0answers
50 views

Number of N Shaped figures formed from the set of points

Given k points on 2d plane and i need to find the number of N shaped figures from these k points. lets consider four different points from the set and name them A,B ,C ,and D (in that order). These ...
4
votes
3answers
56 views

Is there an efficient algorithm to extract the farthest ends of a thin contour?

Let's say you have pixel bitmaps that look something like this: From this I can easily extract a contour, which will be a concave polygon defined by a set of 2D points. The question is what is the ...
5
votes
2answers
76 views

Repeated point in polygon: preprocessing complexity given logarithmic query time?

I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is ...
3
votes
1answer
31 views

Snap/Fit a chain of lines to points

I am looking for an algorithm to fit a chain of lines to a set of points/pixels. I am pretty sure that there is a suitable algorithm but I can't think of the correct search words to find it. Here is ...
1
vote
1answer
32 views

Red-blue intersection requirements

In the red-blue line segments intersection problem, what does it mean that the red-red (and blue-blue) lines cannot intersect? Does mean mean that the algorithms wont work correctly or does it mean ...
3
votes
0answers
59 views

Find internal surfaces in an oriented mesh

I have a solid with internal holes. My solid is mostly a union between walls/floors/ceilings. Each of them is a mesh with polygons oriented counter-clockwise. Then with those polygons I do a union ...
1
vote
1answer
69 views

smallest circle that covers two points with its center in x axis

I have a question about the following problem and the two points need not be located on the circumference of such "smallest circle". I know this is a linear-programming problem but I just don't know ...
0
votes
1answer
64 views

Voronoi Diagram: Exactly 2n-5 vertices

I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices. I tried to use the Euler ...
3
votes
1answer
100 views

Convex hull algorithm in $O(\min(mn, n\log n))$

I am looking for an algorithm to compute the convex hull of a set of $n$ points $P$. The hull should contains $m$ points. This algorithm should work in time $O(\min(mn,n \log n))$. My first guess was ...
4
votes
0answers
34 views

Computing the right tangent of two convex hulls

My question deals with the algorithm of computing the convex hull in 2D by Preparata. Let us assume we have two sets, $A$, $B$, of points in the plane. Let $CH(A)$ and $CH(B)$, denote the convex ...
1
vote
0answers
33 views

Voronoi Diagram Question

I am stuck on that question, it's about Voronoi diagrams Show that for some set of $n$ points, there can be $\Omega(n^2)$ intersections between the edges of the Voronoi diagram and the edges of ...
0
votes
1answer
28 views

Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$

In Python's implementation of $k$-$d$ tree it is possible to manually change the norm used for computing distances from $L^2$ to $L^p$. When would one use a norm other than $L^2$ in a $k$-$d$ tree?
3
votes
1answer
103 views

Finding pairs of points that have a given offset

Problem: Given a set of points $S = \{x_1, x_2, x_3, ..., x_n\}$ from $\mathbb{R}^m$ and an offset vector $v \in \mathbb{R}^m$, find a set $Z \subseteq S \times S$ containing $k$ pairs of points $(x_i,...
1
vote
2answers
96 views

3-SUM hardness vs lower bounds on the complexity

I've recently encountered a new (for me) notion from computational complexity theory called 3-SUM hardness which is based on the conjecture that 3-SUM problem can not be solved in $O\left(n^{2-\...
0
votes
1answer
79 views

Find cell neighbors of a given edge in a 2D grid [closed]

In the figure below, cells are labeled row wise, and edges are labeled counter clockwise. That is, vertices 1' and 2' form edge #1, vertices 2' and 5' form edge #2, vertices 5' and 8' form edge #7, ...
1
vote
0answers
19 views

Bounded pairwise distance on moving points

Suppose you're writing a video game that takes place on a large rectangle (2d). You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and ...
1
vote
1answer
37 views

Is this some kind of hashing?

Say I have $n$ vectors $\{ z_i \in \mathbb{R}^D\}_{i=1}^n$ (where $n$ is very large and hence I can't do any calculation which scales as $n$) and I want to create $n$ vectors $\{x_i \in \mathbb{R}^d \}...
1
vote
0answers
9 views

Optimal locations for vertices of a polygon with given area [closed]

I want to find the optimal locations for vertices of a polygon (with area A) such that it is as close as possible to the desired area A'. Please note that the vertices need not be fixed at their ...
1
vote
0answers
23 views

Optimal bounding boxes selection for $N$ rectangles

Suppose that I have $n$ straight rectangles on a plane $r_i = (x_i,y_i,w_i,h_i)$. Each rectangle has a cost function, its area $A(r_i) = w_i \cdot h_i $. I can also "merge" 2 or more rectangles into ...
1
vote
3answers
223 views

Closest pair of points in a Plane

I want to write an algorithm to find the closest pair of points among n points in an XY-plane. I have the following approach in my mind: Find the minimum x co-ordinate(minX) and minimum y(minY) co-...
6
votes
1answer
86 views

How to find several rectangles with minimum area to cover the red cells

In Figure 1, (a) is the input mesh, we want to find several rectangles to cover the red cells in (a), at the same time, the sum area of these rectangles should be as small as possible. Figure 1(b) and ...
0
votes
2answers
78 views

What is an upright rectangle?

What is an upright rectangle? I came across the phrase in my homework - "The bounding box of a set of S points is the smallest upright rectangle containing S. Describe and analyze an algorithm to ...
2
votes
0answers
48 views

Footprint finding algorithm

I'm trying to come up with an algorithm to optimize the shape of a polygon (or multiple polygons) to maximize the value contained within that shape. I have data with 3 columns: X: the location of ...
2
votes
1answer
39 views

Is there an algorithm that will fill any shape with points a given distance away from each other?

I would like to know if there is an algorithm that if I give a 2D polygon it will give me a set of 2D points. More specifically, those points should have M neighbors that are D apart. The shape is ...
2
votes
0answers
28 views

Optimal way to survey a road

There is a road (a planar curve) of length 1. A treasure is placed in a random spot on the road. The treasure location is a uniform random variable, so that the probability to find the treasure in an ...
5
votes
1answer
54 views

How to detect intersecting segments based on length of the segments

As part of a larger problem, I am trying to detect based on the distance matrix which segments intersect in the original 2D space that originated the matrix. I don´t have coordinates (lat/long, x/y or ...
4
votes
1answer
46 views

Point in Polygon Problem: Has anybody invoked the line integral?

Some twenty years prior I was given the task to solve the Point in Polygon problem for a piece of commercial software. I solved it invoking the ray casting algorithm. After a variety of enhancements ...
6
votes
1answer
49 views

Efficiently split a point cloud into two parts by a hyperplane to maximize the total sum of values associated with one part

I have the following problem in mind. Suppose we have an $n$-dimensional point cloud with $m$ points. Each point in the cloud is associated with a value $X_i,1\leq i\leq m$. I would like to use a ...
6
votes
2answers
76 views

$O(n \log n)$ algorithm for disjoint segment visibility problem

Consider we have $n$ disjoint segments and a point $P$ which is not on any segment. I want to find an $O(n \log n)$ algorithm to check which segments are visible from $P$. A segment is visible from $P$...
5
votes
1answer
48 views

perspective transformation of a grid

A perspective transformation of a point is defined as follows: $ x' = \frac{M_{11}x + M_{12}y +M_{13}}{M_{31}x + M_{32}y +M_{33}} $ $ y' = \frac{M_{21}x + M_{22}y +M_{23}}{M_{31}x + M_{32}y +M_{33}} ...
2
votes
2answers
73 views

How to find the original coordinates of a point inside an irregular rectangle?

I'm a third year computer science student. I'm working on a project Data-show touch screen In schools classrooms. I'll try to explain my problem as much as I can. ...
3
votes
1answer
92 views

How to handle horizontal lines in the Polyfill Algorithm?

When I look at polyfill algorithm tutorials/articles or examples, nothing mentioned about how to handle horizontal lines. Does anyone have any idea how horizontal lines should be handled? For ...
6
votes
1answer
66 views

Voronoi cells for rectangles

I am looking for a reference on the following variant of a Voronoi diagram: Instead of seed points, there are seed rectangles which are axis-parallel and pairwise-disjoint. Instead of Euclidean ...
0
votes
0answers
77 views

Bentley–Ottmann algorithm time complexity issue

In the Bentley–Ottmann algorithm, Regarding : Find the segments r and t that are immediately below and above s in T (if they exist) and if their crossing forms a potential future event in the ...
6
votes
1answer
608 views

Finding a way out of a polygon

There is a simply-connected polygon $C$. It contains $n$ pairwise-interior-disjoint simply-connected polygons, $D_1,\dots,D_n$: The goal is to select one of the polygons, say $D_i$, and attach to ...
3
votes
1answer
99 views

Finding a maximal set of nonintersecting line segments in a unit circle

Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning ...
2
votes
0answers
24 views

3D mesh segmentation simple algorithm

I am developing the algorithm reported in this article: Lest square conformal mapping Here is presented an algorithm to flat a 3d mesh on the parametric space, but i don't understand the ...
5
votes
1answer
92 views

Sort a list of points to form a non-self-intersecting polygon

Given a list (of arbitrary length) of 2-dimensional points, is there some algorithm that I can employ to sort this list of points into an order such that line segments sequentially drawn from $p_0 \...
1
vote
0answers
247 views

Moving a set of points in the plane subject to constraints

I'm new to geometric algorithms and computational geometry, so please forgive me if this is an inappropriate question for this forum. Let $X$ denote the disjoint union of $n$ one-point sets. Let $f:X\...
1
vote
1answer
134 views

Find set of non-overlapping rectangles in a 2D grid

I have a $n \times m$ rectangular grid of cells, and a set $R$ of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned ...