consider:feature-discovery   241
[1710.04640] Hard and Easy Instances of L-Tromino Tilings
In this work we study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we indentify restrictions to the problem where either it remains NP-complete or it has a polynomial time algorithm. First we show that an aztec diamond of order n always has an L-tromino tiling if and only if n(n+1)≡0mod3; if an aztec diamond has at least two defects or holes, however, the problem of deciding a tiling is NP-complete. Then we study tilings of arbitrary regions where only 180∘ rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete, yet, if a region contains certain so-called "forbidden polyominoes" as subregions, then there exists a polynomial time algorithm for deciding a tiling.
polyominoes  tiling  benchmarking  rather-interesting  problem-solving  nudge-targets  consider:feature-discovery
12 days ago by Vaguery
[1405.2378] Covering Folded Shapes
Can folding a piece of paper flat make it larger? We explore whether a shape S must be scaled to cover a flat-folded copy of itself. We consider both single folds and arbitrary folds (continuous piecewise isometries S→R2). The underlying problem is motivated by computational origami, and is related to other covering and fixturing problems, such as Lebesgue's universal cover problem and force closure grasps. In addition to considering special shapes (squares, equilateral triangles, polygons and disks), we give upper and lower bounds on scale factors for single folds of convex objects and arbitrary folds of simply connected objects.
computational-geometry  to-write  paper-folding  rather-interesting  nudge-targets  consider:algorithms  consider:feature-discovery
13 days ago by Vaguery
[1411.6371] Folding a Paper Strip to Minimize Thickness
In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.
paper-folding  computational-geometry  optimization  rather-interesting  to-write-about  to-simulate  nudge-targets  consider:feature-discovery
13 days ago by Vaguery
[1501.00561] A linear-time algorithm for the geodesic center of a simple polygon
Given two points in a simple polygon P of n vertices, its geodesic distance is the length of the shortest path that connects them among all paths that stay within P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack, Sharir and Rote [Disc. \& Comput. Geom. 89] showed an O(nlogn)-time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.
computational-complexity  computational-geometry  optimization  rather-interesting  algorithms  distance  nudge-targets  consider:rediscovery  consider:feature-discovery
14 days ago by Vaguery
[1604.08797] Ortho-polygon Visibility Representations of Embedded Graphs
An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding-preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if G has at most one crossing per edge (i.e., G is a 1-plane graph), an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute an OPVR of G whose vertex complexity is bounded by a constant in O(n) time. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be Ω(n). In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O(n) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs.
graph-layout  computational-geometry  optimization  rather-interesting  to-write-about  nudge-targets  consider:representation  consider:feature-discovery  algorithms  computational-complexity
14 days ago by Vaguery
[1609.06972] Minimal completely asymmetric (4,n)-regular matchstick graphs
A matchstick graph is a graph drawn with straight edges in the plane such that the edges have unit length, and non-adjacent edges do not intersect. We call a matchstick graph $(m,n)$-regular if every vertex has only degree $m$ or $n$. In this article we present the latest known $(4,n)$-regular matchstick graphs for $4\leq n\leq11$ with a minimum number of vertices and a completely asymmetric structure. We call a matchstick graph completely asymmetric, if the following conditions are complied. 1) The graph is rigid. 2) The graph has no point, rotational or mirror symmetry. 3) The graph has an asymmetric outer shape. 4) The graph can not be decomposed into rigid subgraphs and rearrange to a similar graph which contradicts to any of the other conditions.
computational-geometry  graph-theory  rather-interesting  purdy-pitchers  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery
21 days ago by Vaguery
[1512.03421] The extended 1-perfect trades in small hypercubes
An extended 1-perfect trade is a pair (T0,T1) of two disjoint binary distance-4 even-weight codes such that the set of words at distance 1 from T0 coincides with the set of words at distance 1 from T1. Such trade is called primary if any pair of proper subsets of T0 and T1 is not a trade. Using a computer-aided approach, we classify nonequivalent primary extended 1-perfect trades of length 10, constant-weight extended 1-perfect trades of length 12, and Steiner trades derived from them. In particular, all Steiner trades with parameters (5,6,12) are classified.
combinatorics  to-understand  graph-theory  strings  optimization  constraint-satisfaction  looking-to-see  nudge-targets  consider:looking-to-see  consider:classification  consider:feature-discovery
28 days ago by Vaguery
[1006.4176] Unknotting Unknots
A knot is an an embedding of a circle into three-dimensional space. We say that a knot is unknotted if there is an ambient isotopy of the embedding to a standard circle. By representing knots via planar diagrams, we discuss the problem of unknotting a knot diagram when we know that it is unknotted. This problem is surprisingly difficult, since it has been shown that knot diagrams may need to be made more complicated before they may be simplified. We do not yet know, however, how much more complicated they must get. We give an introduction to the work of Dynnikov who discovered the key use of arc--presentations to solve the problem of finding a way to detect the unknot directly from a diagram of the knot. Using Dynnikov's work, we show how to obtain a quadratic upper bound for the number of crossings that must be introduced into a sequence of unknotting moves. We also apply Dynnikov's results to find an upper bound for the number of moves required in an unknotting sequence.
knot-theory  rather-interesting  representation  algorithms  classification  nudge-targets  consider:looking-to-see  consider:feature-discovery
29 days ago by Vaguery
[1605.08396] Robust Downbeat Tracking Using an Ensemble of Convolutional Networks
In this paper, we present a novel state of the art system for automatic downbeat tracking from music signals. The audio signal is first segmented in frames which are synchronized at the tatum level of the music. We then extract different kind of features based on harmony, melody, rhythm and bass content to feed convolutional neural networks that are adapted to take advantage of each feature characteristics. This ensemble of neural networks is combined to obtain one downbeat likelihood per tatum. The downbeat sequence is finally decoded with a flexible and efficient temporal model which takes advantage of the metrical continuity of a song. We then perform an evaluation of our system on a large base of 9 datasets, compare its performance to 4 other published algorithms and obtain a significant increase of 16.8 percent points compared to the second best system, for altogether a moderate cost in test and training. The influence of each step of the method is studied to show its strengths and shortcomings.
neural-networks  music  deep-learning  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery
29 days ago by Vaguery
[cs/0302027] Tiling space and slabs with acute tetrahedra
We show it is possible to tile three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than 77.08∘, and another which tiles a slab in space.
computational-geometry  tiling  rather-interesting  constraint-satisfaction  nudge-targets  consider:feature-discovery  consider:simpler-planar-problem
29 days ago by Vaguery
[1406.5156] Pattern-avoiding permutations and Brownian excursion Part I: Shapes and fluctuations
Permutations that avoid given patterns are among the most classical objects in combinatorics and have strong connections to many fields of mathematics, computer science and biology. In this paper we study the scaling limits of a random permutation avoiding a pattern of length 3 and their relations to Brownian excursion. Exploring this connection to Brownian excursion allows us to strengthen the recent results of Madras and Pehlivan, and Miner and Pak as well as to understand many of the interesting phenomena that had previously gone unexplained.
permutations  combinatorics  review  rather-interesting  feature-extraction  ranimuladom-walks  simulation  nudge-targets  consider:feature-discovery
29 days ago by Vaguery
[1406.0670] Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance
We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) "Fibonacci-automatic". This class includes, for example, the famous Fibonacci word f = 01001010..., the fixed point of the morphism 0 -> 01 and 1 -> 0. We then recover many results about the Fibonacci word from the literature (and improve some of them), such as assertions about the occurrences in f of squares, cubes, palindromes, and so forth. As an application of our method we prove a new result: there exists an aperiodic infinite binary word avoiding the pattern x x x^R. This is the first avoidability result concerning a nonuniform morphism proven purely mechanically.
strings  combinatorics  classification  nudge-targets  consider:looking-to-see  consider:feature-discovery
29 days ago by Vaguery
New Shapes Solve Infinite Pool-Table Problem | Quanta Magazine
Two “rare jewels” have illuminated a mysterious multidimensional object that connects a huge variety of mathematical work.
dynamical-systems  geometry  rather-interesting  mathematical-recreations  nudge-targets  consider:looking-to-see  consider:feature-discovery
5 weeks ago by Vaguery
[1709.05701] Transkingdom Networks: A Systems Biology Approach to Identify Causal Members of Host-Microbiota Interactions
Improvements in sequencing technologies and reduced experimental costs have resulted in a vast number of studies generating high-throughput data. Although the number of methods to analyze these "omics" data has also increased, computational complexity and lack of documentation hinder researchers from analyzing their high-throughput data to its true potential. In this chapter we detail our data-driven, transkingdom network (TransNet) analysis protocol to integrate and interrogate multi-omics data. This systems biology approach has allowed us to successfully identify important causal relationships between different taxonomic kingdoms (e.g. mammals and microbes) using diverse types of data.
rather-interesting  bioinformatics  community-detection  symbiosis  machine-learning  to-write-about  consider:feature-discovery
5 weeks ago by Vaguery
[1404.6238] Recurrence and transience for the frog model on trees
The frog model is a growing system of random walks where a particle is added whenever a new site is visited. A longstanding open question is how often the root is visited on the infinite d-ary tree. We prove the model undergoes a phase transition, finding it recurrent for d=2 and transient for d≥5. Simulations suggest strong recurrence for d=2, weak recurrence for d=3, and transience for d≥4. Additionally, we prove a 0-1 law for all d-ary trees, and we exhibit a graph on which a 0-1 law does not hold.
To prove recurrence when d=2, we construct a recursive distributional equation for the number of visits to the root in a smaller process and show the unique solution must be infinity a.s. The proof of transience when d=5 relies on computer calculations for the transition probabilities of a large Markov chain. We also include the proof for d≥6, which uses similar techniques but does not require computer assistance.
probability-theory  graph-theory  random-walks  dynamical-systems  rather-interesting  to-understand  to-write-about  consider:feature-discovery  consider:classification
6 weeks ago by Vaguery
[1608.08087] Equisectional equivalence of triangles
We study equivalence relation of the set of triangles generated by similarity and operation on a triangle to get a new one by joining division points of three edges with the same ratio. Using the moduli space of similarity classes of triangles introduced by Nakamura and Oguiso, we give characterization of equivalent triangles in terms of circles of Apollonius (or hyperbolic pencil of circles) and properties of special equivalent triangles. We also study rationality problem and constructibility problem.
plane-geometry  compass-and-straightedge  looking-to-see  rather-interesting  algebra  nudge-targets  consider:feature-discovery
6 weeks ago by Vaguery
Unsupervised Sentiment Neuron
It’s interesting to note that the system also makes large updates after the completion of sentences and phrases. For example, in “And about 99.8 percent of that got lost in the film”, there’s a negative update after “lost” and a larger update at the sentence’s end, even though “in the film” has no sentiment content on its own.
sentiment-analysis  neural-networks  machine-learning  natural-language-processing  rather-interesting  to-write-about  consider:cause-and-effect  consider:feature-discovery
7 weeks ago by Vaguery
[1606.02220] Non-aligned drawings of planar graphs
A non-aligned drawing of a graph is a drawing where no two vertices are in the same row or column. Auber et al. showed that not all planar graphs have non-aligned drawings that are straight-line, planar, and in the minimal-possible n×n-grid. They also showed that such drawings exist if up to n−3 edges may have a bend. In this paper, we give algorithms for non-aligned planar drawings that improve on the results by Auber et al. In particular, we give such drawings in an n×n-grid with significantly fewer bends, and we study what grid-size can be achieved if we insist on having straight-line drawings
graph-layout  computational-geometry  algorithms  constraint-satisfaction  rather-interesting  to-write-about  multiobjective-optimization  nudge-targets  consider:feature-discovery
7 weeks ago by Vaguery
[0801.3306] Chip-Firing and Rotor-Routing on Directed Graphs
We give a rigorous and self-contained survey of the abelian sandpile model and rotor-router model on finite directed graphs, highlighting the connections between them. We present several intriguing open problems.
sandpiles  complexology  graph-theory  dynamical-systems  feature-construction  to-write-about  nudge-targets  consider:classification  consider:feature-discovery
7 weeks ago by Vaguery
[1709.05769] Where to Focus: Deep Attention-based Spatially Recurrent Bilinear Networks for Fine-Grained Visual Recognition
Fine-grained visual recognition typically depends on modeling subtle difference from object parts. However, these parts often exhibit dramatic visual variations such as occlusions, viewpoints, and spatial transformations, making it hard to detect. In this paper, we present a novel attention-based model to automatically, selectively and accurately focus on critical object regions with higher importance against appearance variations. Given an image, two different Convolutional Neural Networks (CNNs) are constructed, where the outputs of two CNNs are correlated through bilinear pooling to simultaneously focus on discriminative regions and extract relevant features. To capture spatial distributions among the local regions with visual attention, soft attention based spatial Long-Short Term Memory units (LSTMs) are incorporated to realize spatially recurrent yet visually selective over local input patterns. All the above intuitions equip our network with the following novel model: two-stream CNN layers, bilinear pooling layer, spatial recurrent layer with location attention are jointly trained via an end-to-end fashion to serve as the part detector and feature extractor, whereby relevant features are localized and extracted attentively. We show the significance of our network against two well-known visual recognition tasks: fine-grained image classification and person re-identification.
image-processing  neural-networks  attention  feature-extraction  deep-learning  architecture  constraint-satisfaction  nudge-targets  consider:feature-discovery  consider:representation
7 weeks ago by Vaguery

Copy this bookmark:

description:

tags: