constraint-satisfaction   203
[1808.00626] Slender Origami with Complex 3D Folding Shapes
One-dimensional slender bodies can be deformed or shaped into spatially complex curves relatively easily due to their inherent compliance. However, traditional methods of fabricating complex spatial shapes are cumbersome, prone to error accumulation and not amenable to elegant programmability. In this letter, we introduce a one-dimensional origami based on attaching Miura-ori that can fold into various programmed two or three-dimensional shapes. We study the out-of-plane displacement characteristics of this origami and demonstrate with examples, design of slender bodies that conform to programmed complex spatial curves. Our study provides a new, accurate, and single actuation solution of shape programmability.
origami  engineering-design  nanotechnology  materials-science  self-assembly  rather-interesting  to-write-about  representation  out-of-the-box  constraint-satisfaction  constraint-sidestepping
5 days ago by Vaguery
[1808.06013] Realization and Connectivity of the Graphs of Origami Flat Foldings
We investigate the graphs formed from the vertices and creases of an origami pattern that can be folded flat along all of its creases. As we show, this is possible for a tree if and only if the internal vertices of the tree all have even degree greater than two. However, we prove that (for unbounded sheets of paper, with a vertex at infinity representing a shared endpoint of all creased rays) the graph of a folding pattern must be 2-vertex-connected and 4-edge-connected.
origami  constraint-satisfaction  graph-theory  computational-geometry  rather-interesting  nudge-targets  consider:looking-to-see  consider:feature-discovery
11 days ago by Vaguery
[1606.09402] Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation
Randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-called QB factorization, where Q is an orthonormal matrix. Firstly, a mechanism for calculating the approximation error in Frobenius norm is proposed, which enables efficient adaptive rank determination for large and/or sparse matrix. It can be combined with any QB-form factorization algorithm in which B's rows are incrementally generated. Based on the blocked randQB algorithm by P.-G. Martinsson and S. Voronin, this results in an algorithm called randQB EI. Then, we further revise the algorithm to obtain a pass-efficient algorithm, randQB FP, which is mathematically equivalent to the existing randQB algorithms and also suitable for the fixed-precision problem. Especially, randQB FP can serve as a single-pass algorithm for calculating leading singular values, under certain condition. With large and/or sparse test matrices, we have empirically validated the merits of the proposed techniques, which exhibit remarkable speedup and memory saving over the blocked randQB algorithm. We have also demonstrated that the single-pass algorithm derived by randQB FP is much more accurate than an existing single-pass algorithm. And with data from a scenic image and an information retrieval application, we have shown the advantages of the proposed algorithms over the adaptive range finder algorithm for solving the fixed-precision problem.
numerical-methods  approximation  constraint-satisfaction  algorithms  performance-measure  matrices  to-write-about
6 weeks ago by Vaguery
[1802.03719] Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs
Let Δ={δ1,δ2,...,δm} be a finite set of 2-connected patterns, i.e. graphs up to vertex relabelling. We study the generating function DΔ(z,u1,u2,...,um), which counts polygon dissections and marks subgraph copies of δi with the variable ui. We prove that this is always algebraic, through an explicit combinatorial decomposition depending on Δ. The decomposition also gives a defining system for DΔ(z,0), which encodes polygon dissections that restrict these patterns as subgraphs. In this way, we are able to extract normal limit laws for the patterns when they are encoded, and perform asymptotic enumeration of the resulting classes when they are avoided. The results can be directly transferred in the case of labelled outerplanar graphs. We give examples and compute the relevant constants when the patterns are small cycles or dissections.
combinatorics  graph-theory  permutations  rather-interesting  constraint-satisfaction  enumeration  random-graphs  to-write-about  to-understand
7 weeks ago by Vaguery
[1509.00488] The Tournament Scheduling Problem with Absences
We study time scheduling problems with allowed absences as a new kind of graph coloring problem. One may think of a sport tournament where each player (each team) is permitted a certain number t of absences. We then examine how many rounds are needed to schedule the whole tournament in the worst case. This upper limit depends on t and on the structure of the graph G whose edges represent the games that have to be played, but also on whether or not the absences are announced before the tournament starts. Therefore, we actually have two upper limits for the number of required rounds. We have χt(G) for pre-scheduling if all absences are pre-fixed, and we have χtOL(G) for on-line scheduling if we have to stay flexible and deal with absences when they occur. We conjecture that χt(G)=Δ(G)+2t and that χtOL(G)=χ′(G)+2t. The first conjecture is stronger than the Total Coloring Conjecture while the second is weaker than the On-Line List Edge Coloring Conjecture. Our conjectures hold for all bipartite graphs. For complete graphs, we prove them partially. Lower and upper bounds to χt(G) and χtOL(G) for general multigraphs G are established, too.
combinatorics  graph-theory  graph-coloring  enumeration  queueing-theory  constraint-satisfaction  to-simulate  to-write-about  consider:looking-to-see  consider:feature-discovery
7 weeks ago by Vaguery
[1804.00947] The Transactional Conflict Problem
The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item.
While the standard solution to such conflicts is to immediately abort one of the transactions, some practical systems consider the alternative of delaying conflict resolution for a short interval, which may allow one of the transactions to commit. The challenge in the transactional conflict problem is to choose the optimal length of this delay interval so as to minimize the overall running time penalty for the conflicting transactions. In this paper, we propose a family of optimal online algorithms for the transactional conflict problem.
Specifically, we consider variants of this problem which arise in different implementations of transactional systems, namely "requestor wins" and "requestor aborts" implementations: in the former, the recipient of a coherence request is aborted, whereas in the latter, it is the requestor which has to abort. Both strategies are implemented by real systems.
We show that the requestor aborts case can be reduced to a classic instance of the ski rental problem, while the requestor wins case leads to a new version of this classical problem, for which we derive optimal deterministic and randomized algorithms.
Moreover, we prove that, under a simplified adversarial model, our algorithms are constant-competitive with the offline optimum in terms of throughput.
We validate our algorithmic results empirically through a hardware simulation of hardware transactional memory (HTM), showing that our algorithms can lead to non-trivial performance improvements for classic concurrent data structures.
concurrency  distributed-processing  constraint-satisfaction  asynchronous-dynamics  heuristics  game-theory  mechanism-design  to-simulate  consider:genetic-programming  consider:performance-measures  consider:feature-discovery
7 weeks ago by Vaguery
[1206.2230] Triangle Tiling II: Nonexistence theorems
An N -tiling of triangle ABC by triangle T is a way of writing ABC as a union of N triangles congruent to T, overlapping only at their boundaries. The triangle T is the "tile".
The tile may or may not be similar to ABC . We wish to understand possible tilings by completely characterizing the triples (ABC, T, N) such that ABC can be N -tiled by T. In particular, this understanding should enable us to specify for which N there exists a tile T and a triangle ABC that is N-tiled by T; or given N, determine which tiles and triangles can be used for N-tilings; or given ABC, to determine which tiles and N can be used to N-tile ABC. This is the second of four papers on this subject. In the first paper, we dealt with the case when ABC is similar to T, and the case when T is a right triangle. In this paper, we assume that ABC is not similar to T, and T is not a right triangle, and furthermore that if T has a 120 degree angle, then T is isosceles.
Under those hypotheses, there are only two families of tilings. There are tilings of an equilateral triangle ABC by an isosceles tile with base angles 30 degrees, and there are newly-discovered "triquadratic tilings", which are treated in the third paper in this series. These arise in the special case that 3\alpha + 2\beta = \pi or 3\beta+ 2\alpha = \pi with \alpha not a rational multiple of \pi, where \alpha and \beta are the two smallest angles of the tile, and the sides of the tile have rational ratios.
The case when the tile has a 120 degree angle and is not isosceles is taken up in a subsequent paper.
We use techniques from linear algebra and elementary field theory, and in one case we use some algebraic number theory. We use some counting arguments and some elementary geometry and trigonometry.
tiling  dissection-problems  constraint-satisfaction  proof  combinatorics  nudge-targets  consider:relaxations  consider:approximation
7 weeks ago by Vaguery
[1206.2228] Triangle Tiling V: Tilings by a tile with integer sides
An N-tiling of triangle ABC by triangle T is a way of writing ABC as a union of N triangles congruent to T, overlapping only at their boundaries. The triangle T is the "tile". The tile may or may not be similar to ABC. We wish to understand possible tilings by completely characterizing the triples (ABC, T, N) such that ABC can be N-tiled by T. In particular, this understanding should enable us to specify for which N there exists a tile T and a triangle ABC that is N-tiled by T; or given N, to determine which tiles and triangles can be used for N-tilings; or given ABC, to determine which tiles and N can be used to N-tile ABC. This is the fifth paper in a series of papers on this subject. The previous papers have reduced the problem the case when T has a 120 degree angle and integer side lengths. That is the problem we take up in this paper. We are still not able to completely solve the problem, but we prove that if there are any N-tilings by such tiles, then N is at least 96. Combining this results with our earlier work, we can remove the exception for a tile with a 120 degree angle, obtaining definitive non-existence results. For example, there is no 7-tiling, no 11-tiling, no 14-tiling, no 19-tiling, no 31-tiling, no 41-tiling, etc.
Regarding the number N=96: There are several possible shapes of ABC, and for each shape, we exhibit the smallest N for which it is presently unknown whether there is an N-tiling. For example, for equilateral ABC, the simplest unsolved case as of May, 2012 is N=135. For each of these minimal-N examples, the tile would have to have sides (3,5,7).
tiling  constraint-satisfaction  proof  plane-geometry  dissection-problems  open-questions  consider:looking-to-see  consider:simulation
7 weeks ago by Vaguery
[1811.05437] Argumentation for Explainable Scheduling (Full Paper with Proofs)
Mathematical optimization offers highly-effective tools for finding solutions for problems with well-defined goals, notably scheduling. However, optimization solvers are often unexplainable black boxes whose solutions are inaccessible to users and which users cannot interact with. We define a novel paradigm using argumentation to empower the interaction between optimization solvers and users, supported by tractable explanations which certify or refute solutions. A solution can be from a solver or of interest to a user (in the context of 'what-if' scenarios). Specifically, we define argumentative and natural language explanations for why a schedule is (not) feasible, (not) efficient or (not) satisfying fixed user decisions, based on models of the fundamental makespan scheduling problem in terms of abstract argumentation frameworks (AFs). We define three types of AFs, whose stable extensions are in one-to-one correspondence with schedules that are feasible, efficient and satisfying fixed decisions, respectively. We extract the argumentative explanations from these AFs and the natural language explanations from the argumentative ones.
explaining-how  argumentation  formal-languages  rather-interesting  optimization  constraint-satisfaction  to-write-about  to-understand
7 weeks ago by Vaguery
[1903.11932] Towards the undecidability of atomicity for permutation classes via the undecidability of joint embedding for hereditary graph classes
We work towards answering a question of Ruškuc on the decidability of atomicity for permutation classes, which is equivalent to the decidability of the joint embedding property when permutations are viewed as structures in a language of two linear orders. We begin by showing the corresponding question is undecidable for hereditary graph classes, via a reduction from the tiling problem. After an interlude also showing the undecidability of the joint homomorphism property for hereditary graph classes, we show the undecidability of the joint embedding property for 3-dimensional permutations, i.e. structures in a language of 3 linear orders. Both of these later proofs are obtained by adapting the first proof for hereditary graph classes.
permutations  combinatorics  formal-languages  rather-interesting  graph-theory  stamp-collecting  constraint-satisfaction  representation  to-understand
7 weeks ago by Vaguery
[1206.2231] Triangle Tiling I: The tile is similar to ABC or has a right angle
An N -tiling of triangle ABC by triangle T is a way of writing ABC as a union of N triangles congruent to T, overlapping only at their boundaries. The triangle T is the "tile'".
The tile may or may not be similar to ABC . This paper is the first of several papers, which together seek a complete characterization of the triples (ABC,N,T) such that ABC can be N -tiled by T . In this paper, we consider the case in which the tile is similar to ABC, the case in which the tile is a right triangle, and the case when ABC is equilateral.
We use (only) techniques from linear algebra and elementary field theory, as well as elementary geometry and trigonometry.
Our results (in this paper) are as follows: When the tile is similar to ABC, we always have "quadratic tilings'" when N is a square. If the tile is similar to ABC and is not a right triangle, then N is a square. If N is a sum of two squares, N = e^2 + f^2, then a right triangle with legs e and f can be N -tiled by a tile similar to ABC ; these tilings are called "biquadratic". If the tile and ABC are 30-60-90 triangles, then N can also be three times a square. If T is similar to ABC, these are all the possible triples (ABC, T, N) .
If the tile is a right triangle, of course it can tile a certain isosceles triangle when N is twice a square, and in some cases when N is six times a square.
Equilateral triangles can be 3-tiled and 6-tiled and hence they can also be 3n^2 and 6n^2 tiled for any n . We also discovered a family of tilings when N is 3 times a square, which we call the "hexagonal tilings." These tilings exhaust all the possible triples (ABC, T, N) in case T is a right triangle or is similar to ABC . Other cases are treated in subsequent papers.
tiling  plane-geometry  dissection-problems  constraint-satisfaction  rather-interesting  to-do  enumeration  combinatorics  to-write-about
7 weeks ago by Vaguery
[1206.1974] Tilings of an Isosceles Triangle
An N-tiling of triangle ABC by triangle T is a way of writing ABC as a union of N trianglescongruent to T, overlapping only at their boundaries. The triangle T is the "tile". The tile may or may not be similar to ABC. In this paper we study the case of isosceles (but not equilateral) ABC. There are three possible forms of the tile: right-angled, or with one angle double another, or with a 120 degree angle. We study all three cases. In the case of a right-angled tile, we give a complete characterization of the tilings. In the latter two cases we prove the ratios of the sides of the tile are rational, and give a necessary condition for the existence of an N-tiling. For the case when the tile has one angle double another, we prove N cannot be prime.
tiling  constraint-satisfaction  plane-geometry  dissection-problems  rather-interesting  to-do  to-write-about  consider:looking-to-see  consider:expanded-dissections  consider:algorithms
7 weeks ago by Vaguery
[1812.07014] Tiling an Equilateral Triangle
Let ABC be an equilateral triangle. For certain triangles T (the "tile") and certain N, it is possible to cut ABC into N copies of T. It is known that only certain shapes of T are possible, but until now very little was known about the possible values of N. Here we prove that for N>3, N cannot be prime.
tiling  combinatorics  constraint-satisfaction  plane-geometry  rather-interesting  to-write-about  to-do  to-simulate  consider:looking-to-see  consider:genetic-programming  consider:rediscovery  consider:feature-discovery
7 weeks ago by Vaguery
[1206.2229] Triangle Tiling: The case $3α+ 2β= π$
An N-tiling of triangle ABC by triangle T (the tile') is a way of writing ABC as a union of N copies of T overlapping only at their boundaries. Let the tile T have angles (α,β,γ), and sides (a,b,c). This paper takes up the case when 3α+2β=π. Then there are (as was already known) exactly five possible shapes of ABC: either ABC is isosceles with base angles α, β, or α+β, or the angles of ABC are (2α,β,α+β), or the angles of ABC are (2α,α,2β). In each of these cases, we have discovered, and here exhibit, a family of previously unknown tilings. These are tilings that, as far as we know, have never been seen before. We also discovered, in each of the cases, a Diophantine equation involving N and the (necessarily rational) number s=a/c that has solutions if there is a tiling using tile T of some ABC not similar to T. By means of these Diophantine equations, some conclusions about the possible values of N are drawn; in particular there are no tilings possible for values of N of certain forms. We prove, for example, that there is no N-tiling with N prime when 3α+2β=π. These equations also imply that for each N, there is a finite set of possibilities for the tile (a,b,c) and the triangle ABC. (Usually, but not always, there is just one possible tile.) These equations provide necessary, and in three of the five cases sufficient, conditions for the existence of N-tilings.
tiling  combinatorics  constraint-satisfaction  rather-interesting  to-write-about  to-simulate  mathematical-recreations  consider:looking-to-see  consider:genetic-programming  consider:classification
7 weeks ago by Vaguery
[1805.04055] Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary transformations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration and sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE-completeness of the following decision problems:
∙ Given two satisfying assignments to a planar monotone instance of Not-All-Equal 3-SAT, can one assignment be transformed into the other by single variable flips' (assignment changes), preserving satisfiability at every step?
∙ Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum?
∙ Given two points in {0,1}n contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n-hypercube connecting the two points and contained in P?
These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the instances of the NP problems that appear as input to the reconfiguration problems in our reductions can be shown to lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length.
computational-complexity  discrete-mathematics  optimization  rather-interesting  meta-problems  planning  puzzles  mathematical-recreations  constraint-satisfaction
9 weeks ago by Vaguery
[1705.10239] Fair Division of a Graph
We consider fair allocation of indivisible items under an additional constraint: there is an undirected graph describing the relationship between the items, and each agent's share must form a connected subgraph of this graph. This framework captures, e.g., fair allocation of land plots, where the graph describes the accessibility relation among the plots. We focus on agents that have additive utilities for the items, and consider several common fair division solution concepts, such as proportionality, envy-freeness and maximin share guarantee. While finding good allocations according to these solution concepts is computationally hard in general, we design efficient algorithms for special cases where the underlying graph has simple structure, and/or the number of agents -or, less restrictively, the number of agent types- is small. In particular, despite non-existence results in the general case, we prove that for acyclic graphs a maximin share allocation always exists and can be found efficiently.
assignment-problems  fairness  operations-research  planning  collective-behavior  cake-cutting  game-theory  constraint-satisfaction  rather-interesting  variant-problems  mathematical-recreations  to-write-about  to-simulate
11 weeks ago by Vaguery
Curved Paths
Piecewise circular curves are used in manufacturing, robotics, and highway engineering, but I haven’t found many online references for them. As with circular arcs, piecewise circular curves can handle offsets, distances, and interpolation. Here are some papers I used to learn about circular arcs, biarcs, and piecewise circular curves:
game-design  mathematics  constraint-satisfaction  engineering-design  rather-interesting  aesthetics  the-mangle-in-practice  representation  plane-geometry  parametrization
12 weeks ago by Vaguery
Curating Simulated Storyworlds
There is a peculiar method in the area of procedural narrative called emergent narrative: instead of automatically inventing stories or deploying authored narrative content, a system simulates a storyworld out of which narrative may emerge from the happenstance of character activity in that world. It is the approach taken by some of the most successful works in the history of computational media (The Sims, Dwarf Fortress), but curiously also some of its most famous failures (Sheldon Klein's automatic novel writer, Tale-Spin). How has this been the case? To understand the successes, we might ask this essential question: what is the pleasure of emergent narrative? I contend that the form works more like nonfiction than fiction—emergent stories actually happen—and this produces a peculiar aesthetics that undergirds the appeal of its successful works. What then is the pain of emergent narrative? There is a ubiquitous tendency to misconstrue the raw transpiring of a simulation (or a trace of that unfolding) as being a narrative artifact, but such material will almost always lack story structure.

So, how can the pain of emergent narrative be alleviated while simultaneously maintaining the pleasure? This dissertation introduces a refined approach to the form, called curationist emergent narrative (or just 'curationism'), that aims to provide an answer to this question. Instead of treating the raw material of simulation as a story, in curationism that material is curated to construct an actual narrative artifact that is then mounted in a full-fledged media experience (to enable human encounter with the artifact). This recasts story generation as an act of recounting, rather than invention. I believe that curationism can also explain how both wild successes and phenomenal failures have entered the oeuvre of emergent narrative: in successful works, humans have taken on the burden of curating an ongoing simulation to construct a storied understanding of what has happened, while in the failures humans have not been willing to do the necessary curation. Without curation, actual stories cannot obtain in emergent narrative.

But what if a storyworld could curate itself? That is, can we build systems that automatically recount what has happened in simulated worlds? In the second half of this dissertation, I provide an autoethnography and a collection of case studies that recount my own personal (and collaborative) exploration of automatic curation over the course of the last six years. Here, I report the technical, intellectual, and media-centric contributions made by three simulation engines (World, Talk of the Town, Hennepin) and three second-order media experiences that are respectively driven by those engines (Diol/Diel/Dial, Bad News, Sheldon County). In total, this dissertation provides a loose history of emergent narrative, an apologetics of the form, a polemic against it, a holistic refinement (maintaining the pleasure while killing the pain), and reports on a series of artifacts that represent a gradual instantiation of that refinement. To my knowledge, this is the most extensive treatment of emergent narrative to yet appear.
generative-art  narrative  emergent-design  rather-interesting  to-understand  games  constraint-satisfaction  the-mangle-in-practice  to-read
march 2019 by Vaguery
[PDF] A Survey of Folding and Unfolding in Computational Geometry
Abstract. We survey results in a recent branch of computational geome- try: folding and unfolding of linkages, paper, and polyhedra.
review  origami  computational-geometry  kinematics  constraint-satisfaction  mathematical-recreations  to-write-about
february 2019 by Vaguery

Copy this bookmark:

description:

tags: