The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
46 views

Intersecting balls with convex regions and a bisector thereof

This question is related to my previous posting Angle subtended by the shortest segment that bisects the area of a convex polygon Let $C$ be a convex region in the plane and let $s$ be the shortest ...
2
votes
1answer
252 views

Perimeter of ellipse: Combination of two geometries

Is there a Riemannian metric $g$ on $\mathbb{R}^{2}$ such that for every ellipse $\gamma$ in the plane we have:$$\text{The Euclidien perimeter of}\; \gamma=\lambda (g\text{-diameter ...
1
vote
2answers
95 views

Curves similarity metric [closed]

I am working on an optical character recognition algorithm that takes vector data (i.e. polylines) as input rather than raster picture. E.g., we have N polyline samples, and when certain polyline is ...
6
votes
0answers
641 views

$ n $-Cats-in-a-Bed Problem: Picking $ n $ points in a given planar domain to maximize the sum of their pairwise distances

Let $ C $ be a connected and simply connected compact subset of the plane $ \mathbb{R}^{2} $. How can we pick $ n $ points, denoted $ x_{1},\ldots,x_{n} $, lying in $ C $ such that the total sum $ ...
7
votes
0answers
115 views

Ricocheting pinball-like shot: Complexity?

Suppose one has $n$ perfect two-sided mirror segments in the plane $\mathbb{R}^2$. The segments are open, excluding their endpoints. They are disjoint as closed segments, i.e., no pair shares an ...
4
votes
1answer
71 views

Geometric realization of an abstract triangulation of the plane

Can every abstract simplicial complex whose geometric realization is homeomorphic to $\mathbb{R}^2$ be realized by a rectilinear triangulation of the Euclidean plane? Alternatively put, can a curvy ...
6
votes
2answers
163 views

Geometric dominating set: NP-complete?

Let $G=(V,E)$ be a geometric graph, a graph embedded in the plane whose edge lengths are the Euclidean distance between its endpoint vertices. Say that a set of vertices $D \subseteq V$ is a geometric ...
7
votes
3answers
199 views

Set with small internal radius, small perimeter and prescribed area

Given a regular set $E\subset \mathbb R^2$ define $$ R(E) = \sup\{r\colon \exists x,\ B(x,r)\subseteq E\} $$ to be the radius of the largest circle contained in $E$ and let $|\partial E|$ be the ...
6
votes
3answers
422 views

Polynomial threading through a monotone corridor

I have a need to find a polynomial of minimal degree that connects two points and stays within a given "corridor," by which I mean an $x$-monotone polygon. Here is an example:       ...
1
vote
0answers
174 views

On matrix rank inequality

Let $A$ be a $\{0,1\}$ square matrix. Let $J$ be all $1$ matrix. Let $\bar{A}=J-A$. Is it possible for $rk_+(A)\geq c\cdot rk_+(\bar{A})^d-1$ and $rk_+(\bar{A})\geq c\cdot rk_+({A})^d-1$ for some ...
11
votes
1answer
479 views

Connected components $0-1$ matrices

Let $M$ be a $0-1$ matrix. Here a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where ...
6
votes
0answers
79 views

Unbalanced equipartitions

Let $K$ be a compact convex set in the plane. Say that a perimeter-halving partition of $K$ is a partition of $K$ into two pieces by a chord (a segment with endpoints on the boundary $\partial K$) ...
0
votes
2answers
88 views

Planar curves identical to their inverses

Is the right strophoid the only planar curve $C$ whose inverse curve w.r.t. some circle (in this case: centered on the origin) is identical to $C$?               ...
4
votes
3answers
692 views

Koebe–Andreev–Thurston theorem - where can I find a proof?

Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...
28
votes
2answers
662 views

Term for “uncheckable constructions”

Is there a term for "uncheckable geometric constructions"? Say, Angle Trisection and Doubling the Cube are checkable; i.e., if the answer is given one can do finite Compass-and-straightedge ...
4
votes
1answer
201 views

Panning for gold nuggets: a type of isoperimetric problem

Let $C$ be a unit-radius circle in the plane. Suppose you have a total length $L$ of string available, and your task is to connect chords of $C$ using no more than $L$ of string to minimize the ...
6
votes
4answers
195 views

Inside-out polygonal dissections

A dissection of a polygon $P$ is a partition of $P$ into a finite number of pieces, which can then be rearranged (via planar translations and rotations) and joined (without overlap) to form a new ...
0
votes
2answers
239 views

Determine the boundary points of a set of points [closed]

I have a set of points $S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\}$. Then how to find the boundary points (which is a subset of $S$) of $S$? There are methods like convex hull, concave hull and ...
4
votes
0answers
113 views

Optimal planar net for catching convex shapes

Imagine you want to make a net out of string to filter and catch objects of a certain size, minimizing the length of string employed. (This actually arises in filtering biological impurities from ...
6
votes
2answers
323 views

Are angles between points enough to decide the realizability?

Let n points in the plane be given whose coordinates we don't know. Assume, however, that for any triple of the points we know the angle. Question: Can we decide whether the n points are realizable ...
6
votes
0answers
121 views

A forked plane continuum

I came up with this question while trying to solve the following MO one: Does every connected set that is not a line segment cross some dyadic square? Suppose $C$ is a plane continuum (i.e. a ...
0
votes
0answers
66 views

Intersection points of closed curves inscribed in a convex polygon

Suppose that I have two distinct simple closed curves, $C_1$ & $C_2$, and each is inscribed in a convex polygon, D. By inscribed, I mean tangent to each side of D. In particular, I am most ...
10
votes
1answer
215 views

Schoenberg's Rational Polygon Problem

"A polygon is said to be rational if all its sides and diagonals are rational, and I. J. Schoenberg has posed the difficult question, ‘Can any given polygon be approximated as closely as we like by ...
1
vote
0answers
42 views

Non-Convex Polygons with “Antipodal Visibility”

by "antipodal visibility" of planar, simple polygons I mean the following property: if two points $p$ and $q$ on the polygon's boundary divide the polygon's boundary into two polylines of equal ...
2
votes
2answers
112 views

Maximum possible number of similar three-colored triangles

I want to maximize the number of similar triangles with vertices from three fixed sets, one vertex from each set. For example, if you fix two points $X$, $Y$ (i.e. two sets with only one member), then ...
-3
votes
2answers
136 views

Hexagon Formed by connecting Trisections of triangle sides [closed]

Is there a theorem for the area of the hexagon formed by connecting the points formed when the sides of a triangle are trisected? It appears that the ratio of the area of the triangle to the area of ...
1
vote
1answer
63 views

A quantity associated to a triangle

Let $\Delta ABC$ be a triangle in the plane. Let $P_{1}, P_{2}, P_{3}$ be the intersection points of bisectors, medians and altitudes, respectively. We define the quantity: \begin{equation} Q(\Delta ...
2
votes
1answer
206 views

The points of half area of a triangle

Let $S$ be a simply connected Riemannan surface . Suppose $\Delta ABC$ is a triangle on $S$. The Area of a triangle is denoted by $\mathcal{A}$. A point $P$ in the interior of $\Delta ABC$ is ...
2
votes
1answer
206 views

Distribution of area of randomly placed circles

I've searched the web now for ages to try and find a paper on the asymptotic distribution of the area of the union of randomly placed discs on the plane. Ideally, I would be looking for the discs to ...
6
votes
1answer
141 views

Hiding $k$ disks inside a larger disk

Suppose one has $k$ unit-radius disks, and the goal is to hide them inside a disk of radius $R \gg k$. The detection probes are rays along a line. (Think of the disks as tumor cells, and the rays as ...
4
votes
0answers
175 views

Boundary of an open, bounded and convex set in $\mathbb{R} ^n$

Let $U$ be an open, bounded and convex set in $\mathbb{R} ^n$. Since $\partial U$ is a rectifiable set it follows that up to a set of $H^{n-1}$-measure zero $\partial U$ is contained in a countable ...
1
vote
1answer
35 views

Maximum crossings of curvature-constrained curve

Let $C$ be a curve in the plane whose curvature is everywhere $\le 1$. If $C$ has length $L$, what is the largest number of proper self-crossings of $C$ as a function of $L$? For example, the curve ...
1
vote
1answer
129 views

Vertices of Curves and Eigenvectors of Hessian

This might be a trivial question, but I can't seem to figure it out. Suppose I have an implicitly defined curve in the plane given by $f(x,y) = t$. This curve is strictly convex, and feel free to ...
2
votes
0answers
90 views

What is the projective dual of a planar graph?

Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a ...
6
votes
1answer
170 views

Integral straight-line embeddings of planar graphs

Wikipedia says (in the article on Fáry's theorem), "Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...
3
votes
1answer
204 views

Generalization of notion of convexity

I am searching for the correct term for the following, if it exists. A set $X\subset \mathbb{R}^2$ is called $r$-convex if for any two points $x_1, x_2\in X$ such that there exists an arc of radius ...
5
votes
2answers
440 views

Geometric explanation of Hutton's formula?

$$\frac{\pi}{4} = 2 \tan^{-1} \frac{1}{3} + \tan^{-1} \frac{1}{7} \;.$$ Is there some geometric construction that explains this beautiful equation (known as Hutton's formula)? Perhaps a "proof without ...
3
votes
2answers
322 views

Points contained in a disk [closed]

I have a question, but not sure how to prove this. We are given $n$ points in the Euclidean plane such that there exists no disk of radius $a$ which contains all of the points. Conjecture: There ...
11
votes
2answers
426 views

Triangle with largest perimeter in a convex region

What is the largest value of $r$ such that the following statement is always true? "Let $C$ be a convex region with area $1$. There must exist a triangle contained in $C$ whose perimeter is at least ...
12
votes
1answer
362 views

Probability that random cubic polynomials meet in a square

Let $p_1(x)$ and $p_2(x)$ be cubic polynomials with random coefficients in $[-1,1]$. I wanted to compute the probability that $p_1$ and $p_2$ share at least one point within the square $[-1,1]^2$. Of ...
12
votes
3answers
376 views

Characterization of discs

Let $D$ be a bounded simply connected region (open subset homeomorphic to the disc) in the plane, containing the origin. Suppose that for every line $L$ through the origin the intersection ...
5
votes
1answer
132 views

Maximal regions with given diameter

Let us call a bounded region $D$ in the plane maximal if the conditions $D\subset D'$ and $\mathrm{diam} D'=\mathrm{diam} D$ imply $D'=D$. Is it possible to describe all maximal regions? The only ...
3
votes
1answer
238 views

Planar linkage that traces a circle from its exterior?

Q. Is there a linkage in the plane that traces out a circle $C$ in such a manner that the interior of the disk bounded by $C$ is never intersected by any link througout the motion? What I ...
14
votes
0answers
414 views

Blocking light with mirrored convex objects

There is a long-unsolved problem posed by Janos Pach, sometimes known as the enchanted forest problem, which asks if it is possible to block a point light source in the plane from reaching infinity by ...
33
votes
0answers
506 views

Extending a line-arrangement so that the bounded components of its complement are triangles

Given a finite collection of lines $L_1,\dots,L_m$ in ${\bf{R}}^2$, let $R_1,\dots,R_n$ be the connected components of ${\bf{R}}^2 \setminus (L_1 \cup \dots \cup L_m)$, and say that {$L_1,\dots,L_m$} ...
19
votes
5answers
834 views

Lightray trapped between two mirror disks: Computation formulation?

I would like to calculate the angle of a ray $r$ from a given point $p$ such that it gets "stuck" reflecting between two congruent mirror-disks. For why there is such a ray, see the (amazing!) answer ...
3
votes
1answer
91 views

Generalizations of Directly Similar Theorem?

There is an attractive theorem that says that if two plane figures are directly similar, then so is any convex combination of them. Below, $P_1$ and $P_2$ are directly similar polygons: they have the ...
6
votes
0answers
183 views

Reversing shortest paths among unit disks

Twas the night before Christmas, and throughout M.O. Not a question was posted, not even by Joe. Well, let me remedy that. :-) Let the plane contain a number of ...
6
votes
1answer
169 views

Shortest curve with given convex hull

Suppose $S\subset\mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to S$ is a continuous curve that passes through every extreme point of $S$, i.e., the convex hull of $\Gamma([0,1])$ is $S$. ...
3
votes
1answer
200 views

Map from a convex polygon that increases distance

At the risk of asking an extremely stupid question, suppose that $P\subset\mathbb{R}^2$ is a convex polygon with area $1$ that contains the origin, and let $r$ denote the farthest distance between the ...