inference   1605
[1506.02572] Probing Convex Polygons with a Wedge
Minimizing the number of probes is one of the main challenges in reconstructing geometric objects with probing devices. In this paper, we investigate the problem of using an ω-wedge probing tool to determine the exact shape and orientation of a convex polygon. An ω-wedge consists of two rays emanating from a point called the apex of the wedge and the two rays forming an angle ω. To probe with an ω-wedge, we set the direction that the apex of the probe has to follow, the line L→, and the initial orientation of the two rays. A valid ω-probe of a convex polygon O contains O within the ω-wedge and its outcome consists of the coordinates of the apex, the orientation of both rays and the coordinates of the closest (to the apex) points of contact between O and each of the rays.
We present algorithms minimizing the number of probes and prove their optimality. In particular, we show how to reconstruct a convex n-gon (with all internal angles of size larger than ω) using 2n−2 ω-probes; if ω=π/2, the reconstruction uses 2n−3 ω-probes. We show that both results are optimal. Let NB be the number of vertices of O whose internal angle is at most ω, (we show that 0≤NB≤3). We determine the shape and orientation of a general convex n-gon with NB=1 (respectively NB=2, NB=3) using 2n−1 (respectively 2n+3, 2n+5) ω-probes. We prove optimality for the first case. Assuming the algorithm knows the value of NB in advance, the reconstruction of O with NB=2 or NB=3 can be achieved with 2n+2 probes,- which is optimal.
computational-geometry  inverse-problems  rather-interesting  inference  to-write-about  plane-geometry  algorithms
19 days ago by Vaguery
[1811.00547] Geometric Mean of Partial Positive Definite Matrices with Missing Entries
In this paper the geometric mean of partial positive definite matrices with missing entries is considered. The weighted geometric mean of two sets of positive matrices is defined, and we show whether such a geometric mean holds certain properties which the weighted geometric mean of two positive definite matrices satisfies. Additionally, counterexamples demonstrate that certain properties do not hold. A Loewner order on partial Hermitian matrices is also defined. The known results for the maximum determinant positive completion are developed with an integral representation, and the results are applied to the weighted geometric mean of two partial positive definite matrices with missing entries. Moreover, a relationship between two positive definite completions is established with respect to their determinants, showing relationship between their entropy for a zero-mean,multivariate Gaussian distribution. Computational results as well as one application are shown.
matrices  to-understand  inference  proof  looking-to-see  to-write-about  consider:algorithms  missing-data  data-cleaning
4 weeks ago by Vaguery
[1809.04209] Bidirectional Evaluation with Direct Manipulation
We present an evaluation update (or simply, update) algorithm for a full-featured functional programming language, which synthesizes program changes based on output changes. Intuitively, the update algorithm retraces the steps of the original evaluation, rewriting the program as needed to reconcile differences between the original and updated output values. Our approach, furthermore, allows expert users to define custom lenses that augment the update algorithm with more advanced or domain-specific program updates.
To demonstrate the utility of evaluation update, we implement the algorithm in Sketch-n-Sketch, a novel direct manipulation programming system for generating HTML documents. In Sketch-n-Sketch, the user writes an ML-style functional program to generate HTML output. When the user directly manipulates the output using a graphical user interface, the update algorithm reconciles the changes. We evaluate bidirectional evaluation in Sketch-n-Sketch by authoring ten examples comprising approximately 1400 lines of code in total. These examples demonstrate how a variety of HTML documents and applications can be developed and edited interactively in Sketch-n-Sketch, mitigating the tedious edit-run-view cycle in traditional programming environments.
rather-interesting  usability  functional-languages  computer-science  programming-language  to-understand  inference  ReQ  genetic-programming  consider:GP
5 weeks ago by Vaguery
h2non/filetype: Small, dependency-free and fast Go package to infer file types based on its magic numbers signature
Small, dependency-free and fast Go package to infer file types based on its magic numbers signature - h2non/filetype
golang  filetype  inference  detection
5 weeks ago by pinterb

Copy this bookmark:

description:

tags: