skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Coloring Unit-Distance Strips using SAT
Satisfiability (SAT) solving has become an important technology in computer-aided mathematics with various successes in number and graph theory. In this paper we apply SAT solvers to color infinitely long strips in the plane with a given height and number of colors. The coloring is constrained as follows: two points that are exactly unit distance apart must be colored differently. To finitize the problem, we tile the strips and all points on a tile have the same color. We evaluated our approach using two different tile shapes: squares and hexagons. The visualization of bounded height strips using 3 to 6 colors reveal patterns that are similar to the best known lower bounds for infinite strips. Our method can be a useful tool for mathematicians to search for patterns that can be generalized to infinite strips and allowed us to increase the lower bound for the strip height with 5 colors to an improved height of 1.700084.  more » « less
Award ID(s):
1762363 2006363
PAR ID:
10166356
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
EPiC Series in Computing
Volume:
73
ISSN:
2398-7340
Page Range / eLocation ID:
373 to 355
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, PLOS ONE)
    Mettke-Hofmann, Claudia (Ed.)
    Chemically defended prey often advertise their toxins with bright and conspicuous colors. To understand why such colors are effective at reducing predation, we need to understand the psychology of key predators. In bird predators, there is evidence that individuals avoid novelty—including prey of novel colors (with which they have had no prior experience). Moreover, the effect of novelty is sometimes strongest for colors that are typically associated with aposematic prey (e.g., red, orange, yellow). Given these findings in the bird literature, color neophobia has been argued to be a driving force in the evolution of aposematism. However, no studies have yet asked whether invertebrate predators respond similarly to novel colors. Here, we tested whether naive lab-raised jumping spiders ( Habronattus pyrrithrix ) exhibit similar patterns of color neophobia to birds. Using color-manipulated living prey, we first color-exposed spiders to prey of two out of three colors (blue, green, or red), with the third color remaining novel. After this color exposure phase, we gave the spiders tests where they could choose between all three colors (two familiar, one novel). We found that H . pyrrithrix attacked novel and familiar-colored prey at equal rates with no evidence that the degree of neophobia varied by color. Moreover, we found no evidence that either prey novelty nor color (nor their interaction) had an effect on how quickly prey was attacked. We discuss these findings in the context of what is known about color neophobia in other animals and how this contributes to our understanding of aposematic signals. 
    more » « less
  2. ; ; ; ; (, Integrative and Comparative Biology)
    Abstract Community science, which engages students and the public in data collection and scientific inquiry, is often integrated into conservation and long-term monitoring efforts. However, it has the potential to also introduce the public to, and be useful for, sensory ecology and other fields of study. Here we describe a community science project that exposes participants to animal behavior and sensory ecology using the rich butterfly community of Northwest Arkansas, United States. Butterflies use visual signals to communicate and to attract mates. Brighter colors can produce stronger signals for mate attraction but can also unintentionally attract negative attention from predators. Environmental conditions such as weather can affect visual signaling as well, by influencing the wavelengths of light available and subsequent signal detection. However, we do not know whether the signals butterflies present correlate broadly with how they behave. In this study, we collaborated with hundreds of students and community members at the University of Arkansas (UARK) and the Botanical Gardens of the Ozarks (BGO) for over 3.5 years to examine relationships among wing pattern, weather, time of day, behavior, and flower choice. We found that both weather and wing color influenced general butterfly behavior. Butterflies were seen feeding more on cloudy days than on sunny or partly cloudy days. Brown butterflies fed or sat more often, while white butterflies flew more often relative to other butterfly colors. We also found that there was an interaction between the effects of weather and wing color on butterfly behavior. Furthermore, butterfly color predicted the choice of flower colors that butterflies visited, though this effect was influenced by the observer group (UARK student or BGO participant). These results suggest that flower choice may be associated with butterfly wing pattern, and that different environmental conditions may influence butterfly behavior in wing-pattern–specific ways. They also illustrate one way that public involvement in behavioral studies can facilitate the identification of coarse-scale, community-wide behavioral patterns, and lay the groundwork for future studies of sensory niches. 
    more » « less
  3. ; ; (, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022))
    We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology. It relies on four sub-algorithms that alternatingly compute cliques of larger size and colorings with fewer colors. We show how these techniques can mutually help each other: larger cliques facilitate finding smaller colorings, which in turn can boost finding larger cliques. We evaluate our approach on the DIMACS graph coloring suite. For finding maximum cliques, we show that our algorithm can improve the state-of-the-art MaxSAT-based solver IncMaxCLQ, and for the graph coloring problem, we close two open instances, decrease two upper bounds, and increase one lower bound. 
    more » « less
  4. ; ; ; ; (, Research in Computational Molecular Biology)
    The colored de Bruijn graph (cdbg) and its variants have become an important combinatorial structure used in numerous areas in genomics, such as population-level variation detection in metagenomic samples, large scale sequence search, and cdbg-based reference sequence indices. As samples or genomes are added to the cdbg, the color information comes to dominate the space required to represent this data structure. In this paper, we show how to represent the color information efficiently by adopting a hierarchical encoding that exploits correlations among color classes—patterns of color occurrence—present in the de Bruijn graph (dbg). A major challenge in deriving an efficient encoding of the color information that takes advantage of such correlations is determining which color classes are close to each other in the high-dimensional space of possible color patterns. We demonstrate that the dbg itself can be used as an efficient mechanism to search for approximate nearest neighbors in this space. While our approach reduces the encoding size of the color information even for relatively small cdbgs (hundreds of experiments), the gains are particularly consequential as the number of potential colors (i.e. samples or references) grows into the thousands. We apply this encoding in the context of two different applications; the implicit cdbg used for a large-scale sequence search index, Mantis, as well as the encoding of color information used in population-level variation detection by tools such as Vari and Rainbowfish. Our results show significant improvements in the overall size and scalability of representation of the color information. In our experiment on 10,000 samples, we achieved more than 11× better compression compared to RRR. 
    more » « less
  5. ; ; (, ACM Symposium on User Interface Software and Technology (UIST))
    We propose a novel system for low-cost multi-color Fused Filament Fabrication (FFF) 3D printing, allowing for the creation of customizable colored filament using a pre-processing approach. We developed an open-source device to automatically ink filament using permanent markers. Our device can be built using 3D printed parts and off-the-shelf electronics. An accompanying web-based interface allows users to view GCODE toolpaths for a multi-color print and quickly generate filament color profiles. Taking a pre-processing approach makes this system compatible with the majority of desktop 3D printers on the market, as the processed filament behaves no differently from conventional filaments. Furthermore, inked filaments can be produced economically, reducing the need for excessive purchasing of material to expand color options. We demonstrate the efficacy of our system by fabricating monochromatic objects, objects with gradient colors, objects with bi-directional properties, as well as multi-color objects with up to four colors in a single print. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email