Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistinct Angle Problems and Variants
137
0
0.0
(
0
)
Added by
Charles Wolf
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The ErdH{o}s distinct distance problem is a ubiquitous problem in discrete geometry. Less well known is ErdH{o}s distinct angle problem, the problem of finding the minimum number of distinct angles between $n$ non-collinear points in the plane. The standard problem is already well understood. However, it admits many of the same variants as the distinct distance problem, many of which are unstudied. We provide upper and lower bounds on a broad class of distinct angle problems. We show that the number of distinct angles formed by $n$ points in general position is $O(n^{log_2(7)})$, providing the first non-trivial bound for this quantity. We introduce a new class of asymptotically optimal point configurations with no four cocircular points. Then, we analyze the sensitivity of asymptotically optimal point sets to perturbation, yielding a much broader class of asymptotically optimal configurations. In higher dimensions we show that a variant of Lenzs construction admits fewer distinct angles than the optimal configurations in two dimensions. We also show that the minimum size of a maximal subset of $n$ points in general position admitting only unique angles is $Omega(n^{1/5})$ and $O(n^{log_2(7)/3})$. We also provide bounds on the partite variants of the standard distinct angle problem.
rate research
Read More
We study a variant of the ErdH os unit distance problem, concerning angles between successive triples of points chosen from a large finite point set. Specifically, given a large finite set of $n$ points $E$, and a sequence of angles $(alpha_1,ldots,alpha_k)$, we give upper and lower bounds on the maximum possible number of tuples of distinct points $(x_1,dots, x_{k+2})in E^{k+2}$ satisfying $angle (x_j,x_{j+1},x_{j+2})=alpha_j$ for every $1le j le k$ as well as pinned analogues.
We show that the maximum number of pairwise non-overlapping $k$-rich lenses (lenses formed by at least $k$ circles) in an arrangement of $n$ circles in the plane is $Oleft(frac{n^{3/2}log{(n/k^3)}}{k^{5/2}} + frac{n}{k} right)$, and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is $Oleft(frac{n^{3/2}log{(n/k^3)}}{k^{3/2}} + nright)$. Two independent proofs of these bounds are given, each interesting in its own right (so we believe). We then show that these bounds lead to the known bound of Agarwal et al. (JACM 2004) and Marcus and Tardos (JCTA 2006) on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.
Given a set of points in the Euclidean plane, the Euclidean textit{$delta$-minimum spanning tree} ($delta$-MST) problem is the problem of finding a spanning tree with maximum degree no more than $delta$ for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean textit{$delta$-minimum bottleneck spanning tree} ($delta$-MBST) problem, is the problem of finding a degree-bounded spanning tree for a set of points in the plane such that the length of the longest edge is minimum. When $delta leq 4$, these two problems may yield disjoint sets of optimal solutions for the same set of points. In this paper, we perform computational experiments to compare the accuracies of a variety of heuristic and approximation algorithms for both these problems. We develop heuristics for these problems and compare them with existing algorithms. We also describe a new type of edge swap algorithm for these problems that outperforms all the algorithms we tested.
We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called textit{codemaker} constructs a hidden sequence $H = (h_1, h_2, ldots, h_n)$ of colors selected from an alphabet $mathcal{A} = {1,2,ldots, k}$ (textit{i.e.,} $h_iinmathcal{A}$ for all $iin{1,2,ldots, n}$). The game then proceeds in turns, each of which consists of two parts: in turn $t$, the second player (the textit{codebreaker}) first submits a query sequence $Q_t = (q_1, q_2, ldots, q_n)$ with $q_iin mathcal{A}$ for all $i$, and second receives feedback $Delta(Q_t, H)$, where $Delta$ is some agreed-upon function of distance between two sequences with $n$ components. The game terminates when $Q_t = H$, and the codebreaker seeks to end the game in as few turns as possible. Throughout we let $f(n,k)$ denote the smallest integer such that the codebreaker can determine any $H$ in $f(n,k)$ turns. We prove three main results: First, when $H$ is known to be a permutation of ${1,2,ldots, n}$, we prove that $f(n, n)ge n - loglog n$ for all sufficiently large $n$. Second, we show that Knuths Minimax algorithm identifies any $H$ in at most $nk$ queries. Third, when feedback is not received until all queries have been submitted, we show that $f(n,k)=Omega(nlog k)$.
In this paper, we are concerned with geometric constraint solvers, i.e., with programs that find one or more solutions of a geometric constraint problem. If no solution exists, the solver is expected to announce that no solution has been found. Owing to the complexity, type or difficulty of a constraint problem, it is possible that the solver does not find a solution even though one may exist. Thus, there may be false negatives, but there should never be false positives. Intuitively, the ability to find solutions can be considered a measure of solvers competence. We consider static constraint problems and their solvers. We do not consider dynamic constraint solvers, also known as dynamic geometry programs, in which specific geometric elements are moved, interactively or along prescribed trajectories, while continually maintaining all stipulated constraints. However, if we have a solver for static constraint problems that is sufficiently fast and competent, we can build a dynamic geometry program from it by solving the static problem for a sufficiently dense sampling of the trajectory of the moving element(s). The work we survey has its roots in applications, especially in mechanical computer-aided design (MCAD). The constraint solvers used in MCAD took a quantum leap in the 1990s. These approaches solve a geometric constraint problem by an initial, graph-based structural analysis that extracts generic subproblems and determines how they would combine to form a complete solution. These subproblems are then handed to an algebraic solver that solves the specific instances of the generic subproblems and combines them.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
