**consider:feature-discovery**241

[1710.04640] Hard and Easy Instances of L-Tromino Tilings

12 days ago by Vaguery

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

13 days ago by Vaguery

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

13 days ago by Vaguery

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

14 days ago by Vaguery

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

14 days ago by Vaguery

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

21 days ago by Vaguery

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

28 days ago by Vaguery

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

29 days ago by Vaguery

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

29 days ago by Vaguery

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

29 days ago by Vaguery

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

29 days ago by Vaguery

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

29 days ago by Vaguery

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

5 weeks ago by Vaguery

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

5 weeks ago by Vaguery

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

6 weeks ago by Vaguery

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
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.

6 weeks ago by Vaguery

[1608.08087] Equisectional equivalence of triangles

6 weeks ago by Vaguery

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

7 weeks ago by Vaguery

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

7 weeks ago by Vaguery

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

7 weeks ago by Vaguery

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

7 weeks ago by Vaguery

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

**related tags**

Copy this bookmark: