# Tagged Questions

25 views

### Working algorithm for testing two rectangles for overlapping in Earth GPS coordinates plain

Here is a seemingly simple, but actually quite tricky problem: I am trying to figure out the correct algorithm to test intersection/overlapping of two rectangles, which are plotted on the Earth's ...
15 views

### Calculate the fraction of volume of a rectilinear grid cell within some radius of the origin

I have a sphere (radius $R$) on a rectilinear grid. Some cells intersect the edge of that sphere, call them 'edge cells'. Designate a given cell by indices $[i,j,k]$ which refer to the lowest-index ...
38 views

### Number of ways to make grid

I need to construct a L x 3 grid as shown below But i can use only two shapes to make it which are : Here L is the number of small square boxes in each row. I can rotate the shapes as I want. I ...
18 views

### How to identify a variable-sized zone by a point given by coordinate?

The Cartesian plane is partitioned into zones of variable sizes. A zone is always a rectangle. For example, a zone can be represented like $x \in (0, 3], y \in (30, 50]$ The range in the Cartesian ...
33 views

### Room for computational geometry in advanced algorithms course

I am currently putting together an independent study in advanced algorithms and because of my interest in (computational) geometry, wanted to include as many interesting algorithms from this field as ...
104 views

### Number of classes of K-sets

I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}. I need to to know how many K-sets exist(here K-set refers to ...
47 views

### Calculate geometry created by “slicing” rectangle with lines

Given a rectangle with a series lines intersecting it, how would you calculate the points of each individual shape created? In this particular application that we are working on, the user can "slice" ...
159 views

### Maximum Area of rectangle without any monsters

Moderator's note: the lock on this question from Jan 6, 2013 until Jan 13, 2013 is due to its being an active contest question on CodeChef. The question will be unlocked automatically after the end ...
45 views

### given point lies inside or outside a polygon

I was trying this question and found a solution : Draw a horizontal line to the right of each point and extend it to infinity ...
50 views

### Determining box-box intersection without cross product

Does anyone know a way to correctly determine if an axis-aligned box intersects with an oriented (using any invertible square matrix) box in a space with three or more dimensions, without using cross ...
33 views

### Which icosahedral triangles projected onto sphere's surface contain points in P?

I am working on a Python script to: Compute the vertex coordinates of a geodesic sphere/icosahedron, Project the triangles onto a sphere, then Find which spherical triangle contains an arbitrary ...
68 views

### Megiddo's algorithm for lines of least weighted sum distance from a set of points

I came across the following problem: Given a set of n points (coordinate in 2d plane) within a rectangular space, find out a line ($ax+by=c$), from which the sum of the perpendicular distances of all ...
67 views

### Finding the “middle 2” of four lines

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle. This problem works in 2-dimensional Euclidean space. A ...
60 views

### How to generate the n-simplex?

I was following this wikipedia section, in the simplex article to see if I could create a MATLAB algorithm to generate a simplex with $n$ points in 3-dimensional space. Sure enough it works for 4 ...
36 views

### Selecting k vectors with maximum spread out of a set of n vectors

Given a set $\mathcal{V}$ of $n$ vectors, find a subset $\mathcal{V}_k = \mathcal{V} - \mathcal{V}_{n-k}$ containing $k$ maximally spread vectors. Intuitively, these $k$ vectors should be spread as ...
72 views

### Shortest path calculation

I have a given set of start points, a given set of end points. Each start point corresponds to one endpoint. I have to visit all start points, and then the corresponding end points, in the most ...
68 views

### First event in a straight skeleton

Is there a simple geometric criterion to check whether the first event in (the wave propagation of) a straight skeleton is an edge event or a split event? The literature I could find is computational ...
55 views

### Meet of lines in n-dimension.

I am searching for a general approach to use in a script for determining if two n-dimensional lines represented by one point and their direction vector are skew, parallel, intersecting or identical. ...
206 views

### Distance of two Rectangle Center's Connecting Line Outside of the Rectangles

Well excuse me for the long title, i dont really know how to call it. I would like you to explain me how to calculate the image's red line's length, knowing the rectangles position and dimensions. ...
67 views

### Bending of track in a racing game

I am trying to create a small racing game in which the track would be modeled using a BSpline curve for the path's center line and directional vectors to define the 'bending' of the track at each ...
163 views

### Finding the largest circle that contains a single point in a set (and no other point)

Given a bounded $A \times B$ rectangle with a set of chosen coordinates, generated for example with the command: ...
62 views

### Generalized Straight Skeleton

The straight skeleton of a polygon can be computed by having the edges of the polygon move inwards at a uniform constant speed. Is it useful to generalize this computation process by varying the ...
902 views

### Algorithm to get the maximum size of n squares that fit into a rectangle with a given width and height

I am looking for an algorithm that can return the number of size of n squares that fit into a a rectangle of a given width and height, maximizing the use of space (thus, leaving the least amount of ...
129 views

### Minimize the sum of distance under maximum norm

Given a set of points (Xi, Yi). I need to find a point (doesn't have to be in the given set) that minimize the sum of distance to the other points. The tricky part is the distance is measured by ...
108 views

### How to calculate a PHI-ellipse defined by 3 points and its width/length ratio

in the field of technical analysis for stock markets, the usage of so-called Phi-Ellipses is getting popular. One important property of this ellipses is its constant length/width ratio (e.g. 1.618). ...