In computer science theory – particularly formal language theory – Glushkov's construction algorithm, invented by Victor Mikhailovich Glushkov, transforms a given regular expression into an equivalent nondeterministic finite automaton (NFA). Thus, it forms a bridge between regular expressions and nondeterministic finite automata: two abstract representations of the same class of formal languages. A regular expression may be used to conveniently describe an advanced search pattern in a "find and replace"–like operation of a text processing utility. Glushkov's algorithm can be used to transform it into an NFA, which furthermore is small by nature, as the number of its states equals the number of symbols of the regular expression, plus one. Subsequently, the NFA can be made deterministic by the powerset construction and then be minimized to get an optimal automaton corresponding to the given regular expression. The latter format is best suited for execution on a computer. From another, more theoretical point of view, Glushkov's algorithm is a part of the proof that NFA and regular expressions both accept exactly the same languages; that is, the regular languages. The converse of Glushkov's algorithm is Kleene's algorithm, which transforms a finite automaton into a regular expression. The automaton obtained by Glushkov's construction is the same as the one obtained by Thompson's construction algorithm, once its ε-transitions are removed. Glushkov's construction algorithm is also called The algorithm of Berry-Sethi, named after Gérard Berry and Ravi Sethi who worked on this construction. == Construction == Given a regular expression e, the Glushkov Construction Algorithm creates a non-deterministic automaton that accepts the language L ( e ) {\displaystyle L(e)} accepted by e. The construction uses four steps: === Step 1 === Linearisation of the expression. Each letter of the alphabet appearing in the expression e is renamed, so that each letter occurs at most once in the new expression e ′ {\displaystyle e'} . Glushkov's construction essentially relies on the fact that e ′ {\displaystyle e'} represents a local language L ( e ′ ) {\displaystyle L(e')} . Let A be the old alphabet and let B be the new one. === Step 2a === Computation of the sets P ( e ′ ) {\displaystyle P(e')} , D ( e ′ ) {\displaystyle D(e')} , and F ( e ′ ) {\displaystyle F(e')} . The first, P ( e ′ ) {\displaystyle P(e')} , is the set of letters which occurs as first letter of a word of L ( e ′ ) {\displaystyle L(e')} . The second, D ( e ′ ) {\displaystyle D(e')} , is the set of letters that can end a word of L ( e ′ ) {\displaystyle L(e')} . The last one, F ( e ′ ) {\displaystyle F(e')} , is the set of letter pairs that can occur in words of L ( e ′ ) {\displaystyle L(e')} , i.e. it is the set of factors of length two of the words of L ( e ′ ) {\displaystyle L(e')} . Those sets are mathematically defined by P ( e ′ ) = { x ∈ B ∣ x B ∗ ∩ L ( e ′ ) ≠ ∅ } {\displaystyle P(e')=\{x\in B\mid xB^{}\cap L(e')\neq \emptyset \}} , D ( e ′ ) = { y ∈ B ∣ B ∗ y ∩ L ( e ′ ) ≠ ∅ } {\displaystyle D(e')=\{y\in B\mid B^{}y\cap L(e')\neq \emptyset \}} , F ( e ′ ) = { u ∈ B 2 ∣ B ∗ u B ∗ ∩ L ( e ′ ) ≠ ∅ } {\displaystyle F(e')=\{u\in B^{2}\mid B^{}uB^{}\cap L(e')\neq \emptyset \}} . They are computed by induction over the structure of the expression, as explained below. === Step 2b === Computation of the set Λ ( e ′ ) {\displaystyle \Lambda (e')} which contains the empty word ε {\displaystyle \varepsilon } if this word belongs to L ( e ′ ) {\displaystyle L(e')} , and is the empty set otherwise. Formally, this is Λ ( e ′ ) = { ε } ∩ L ( e ′ ) {\displaystyle \Lambda (e')=\{\varepsilon \}\cap L(e')} . === Step 3 === Computation of automaton recognizing the local language, as defined by P ( e ′ ) {\displaystyle P(e')} , D ( e ′ ) {\displaystyle D(e')} , F ( e ′ ) {\displaystyle F(e')} , and Λ ( e ′ ) {\displaystyle \Lambda (e')} . By definition, the local language defined by the sets P, D, and F is the set of words which begin with a letter of P, end by a letter of D, and whose factors of length 2 belong to F, optionally also including the empty word; that is, it is the language: L ′ = ( P B ∗ ∩ B ∗ D ) ∖ B ∗ ( B 2 ∖ F ) B ∗ ∪ Λ ( e ′ ) {\displaystyle L'=(PB^{}\cap B^{}D)\setminus B^{}(B^{2}\setminus F)B^{}\cup \Lambda (e')} . Strictly speaking, it is the computation of the automaton for the local language denoted by this linearised expression that is Glushkov's construction. === Step 4 === Remove the linearisation, replacing each indexed letter B by the original letter of A. == Example == Consider the regular expression e = ( a ( a b ) ∗ ) ∗ + ( b a ) ∗ {\displaystyle e=(a(ab)^{})^{}+(ba)^{}} . == Computation of the set of letters == The computation of the sets P, D, F, and Λ is done inductively over the regular expression e ′ {\displaystyle e'} . One must give the values for ∅, ε (the symbols for the empty language and the singleton language containing the empty word), the letters, and the results of the operations + , ⋅ , ∗ {\displaystyle +,\cdot ,^{}} . The most costly operations are the cartesian products of sets for the computation of F. == Properties == The obtained automaton is non-deterministic, and it has as many states as the number of letters of the regular expression, plus one. It has been proven that every Thompson's automaton can be transformed into Glushkov's automaton via a ε-transitions elimination method. == Applications and deterministic expressions == The computation of the automaton by the expression occurs often; it has been systematically used in search functions, in particular by the Unix grep command. Similarly, XML's specification also uses such constructions; for more efficiency, regular expressions of a certain kind, called deterministic expressions, have been studied.
Pill reminder
A pill reminder is any device that reminds users to take medications. Traditional pill reminders are pill containers with electric timers attached, which can be preset for certain times of the day to set off an alarm. More sophisticated pill reminders can also detect when they have been opened, and therefore when the user is away during the time they were supposed to take their medication, they will be reminded of it when they return. This reminder can be in the form of a light, which also helps for deaf or hearing-impaired users. == Mobile app == A newer type of pill reminder is a mobile app that reminds the owner to take the medication. Some of these applications might effectively support adherence to taking medications.
Recraft
Recraft is a generative artificial intelligence program and service developed by the London-based startup Recraft, Inc. The company also offers Recraft Studio, a web-based workspace that lets users create and edit images, vectors, and mockups using various text-to-image models. Like models such as Midjourney and DALL-E, the Recraft model generates digital images from natural language prompts, and is specifically tailored for creative workflows, with features that emphasize brand consistency, text fidelity, and layout control. == History and background == Recraft, Inc. was founded in 2022 by machine learning scientist Anna Veronika Dorogush, best known for co-creating the CatBoost machine learning library at Yandex. The company emerged from stealth on May 31, 2023, with a public release of its vector graphics generation capability on Product Hunt. On January 17, 2024, TechCrunch profiled Recraft’s foundational model for graphic design, noting its emphasis on addressing copyright and ethical concerns associated with AI-generated imagery. On October 28, 2024, TechCrunch reported that Recraft's third major model, V3, had topped a crowdsourced benchmark, surpassing Midjourney and OpenAI's DALL-E in overall image quality. On May 5, 2025, Recraft announced a $30 million Series B funding round led by Accel, reporting more than four million registered users at the time of the announcement. == Models == Recraft has developed multiple generations of its text-to-image models since 2022. Each generation reflects improvements in fidelity, controllability, and support for both raster and vector outputs. The models are proprietary and accessible through the Recraft API, Recraft Studio. Recraft models are also hosted as an image generation API on fal, Replicate, Prodia, and others. === Recraft V2 === Recraft V2 was released in March 2024 and was the company’s first model trained from scratch. It contained roughly 20 billion parameters and introduced native vector image generation, brand-color conditioning, and improved stylistic consistency for icons and illustrations. === Recraft V3 === Recraft V3 was released in October 2024 and achieved first place on the Artificial Analysis benchmark hosted on Hugging Face. The model introduced advances in photorealism, improved rendering of multi-word text, and increased responsiveness to detailed descriptive prompts. It also added the “Artistic” parameter, which allowed users to adjust stylistic intensity within generated images. === Recraft V4 === Recraft V4 was released in February 2026. According to Recraft, V4 is a “ground-up rebuild” aimed at improving prompt accuracy and output quality for design workflows, with the company emphasizing “design taste” and art-directed results. Recraft states that V4 is available in two versions: V4 for faster iteration and V4 Pro for higher-resolution, print-ready assets; the API documentation describes V4 as 1-megapixel output and V4 Pro as 4-megapixel output, with vector variants available for each. === Features === Vectorization: Recraft’s models can generate and convert images into native vector formats, producing scalable graphics composed of editable paths rather than fixed pixels. Style reference: The models support the use of reference images to guide stylistic characteristics such as color palette, line quality, composition, or visual tone. Style mixing: Recraft models can combine multiple stylistic inputs within a single generation. By blending attributes from different references or stylistic instructions, the system produces images that reflect hybrid visual characteristics while maintaining internal consistency. Inpainting editing: The models support localized image modification through inpainting, enabling users to regenerate selected regions of an image while preserving surrounding content. === Model capabilities === Recraft’s models generate raster and vector images from natural-language prompts and are designed to interpret detailed descriptions with attention to composition, style, and text placement. The models support controlled stylistic variation through preset or reference-based guidance and can maintain coherent line, color, or layout structure across multiple outputs. They produce scalable vector graphics alongside high-resolution raster images, and include features for localized image modification through inpainting or outpainting operations. === Technology === Recraft has not publicly disclosed the detailed technical architecture of its models. However, third-party reviews and benchmarks have noted that its performance resembles diffusion models such as Midjourney and Stable Diffusion. The model is designed for creative workflows requiring visual consistency and flexible output formats. Reviewers have noted its ability to generate legible multi-line text, produce high-resolution imagery at various canvas sizes, and to maintain alignment with user-defined brand palettes and design themes. Though not open-source, Recraft's models are accessible through a web interface and commercial API. Advanced features such as style settings and positioning control differentiate it from general-purpose text-to-image models. == Recraft Studio == Recraft Studio is a web-based workspace for generating and editing images using Recraft’s image models and selected external models. The infinite canvas interface provides access to a range of creation and refinement tools within a single environment. Raster and vector generation with styles: Recraft Studio supports the generation of both raster and vector images. Users can apply predefined or reference-based styles during generation, allowing for visual consistency across multiple outputs. Mockups: The studio includes mockup tools that allow generated designs to be placed onto predefined surfaces or templates for visualization and presentation purposes. Vectorization: Recraft Studio provides vectorization tools that convert raster images into editable vector graphics, enabling further modification of shapes, colors, and layout. Image upscaling: The workspace includes image upscaling functionality for increasing resolution while preserving visual detail. Editing tools and natural-language editing: Recraft Studio offers a set of editing tools for modifying images within the canvas, including localized adjustments and natural-language–based editing commands that allow users to describe changes using text. === Supported models === Recraft Studio provides access to Recraft’s proprietary image models as well as other external frontier image models such as Nano Banana, GPT 4-o, Imagen, Flux, and others. == Business model == Recraft develops proprietary image models that are accessible through Recraft Studio and the Recraft API. Recraft Studio operates on a freemium model, offering a free tier with limited daily credits and paid subscriptions for access to additional features. The API follows a credit-based system in which units are purchased separately for programmatic image generation. A team plan supports collaborative use, and the API enables organizations and developers to integrate Recraft’s image generation and editing capabilities into their own systems and workflows.
Vibe coding
Vibe coding is a software development practice assisted by artificial intelligence (AI) where the software developer describes a project or task in a prompt to a large language model (LLM), which generates source code automatically. Vibe coding may involve accepting AI-generated code without thorough review of the output, instead relying on results and follow-up prompts to guide changes. The term was coined in February 2025 by computer scientist Andrej Karpathy, a co-founder of OpenAI and former AI leader at Tesla. Merriam-Webster listed the term in March 2025 as a "slang & trending" expression. It was named the Collins English Dictionary Word of the Year for 2025. Advocates of vibe coding say that it allows even amateur programmers to produce software without the extensive training and skills required for software engineering. Critics point out a lack of accountability, maintainability, and the increased risk of introducing security vulnerabilities in the resulting software. == Definition == The concept refers to a coding approach that relies on LLMs, allowing programmers to generate working code by providing natural language descriptions rather than manually writing in a formal programming language. Karpathy described it as a form of coding where you "fully give in to the vibes, embrace exponentials, and forget that the code even exists". When vibe coding, the programmer guides, tests, and gives feedback about the AI-generated source code, rather than manually writing code. The concept of vibe coding elaborates on Karpathy's claim from 2023 that "the hottest new programming language is English", meaning that the capabilities of LLMs were such that humans would no longer need to learn specific programming languages to command computers. Some commentators argue that a key to the definition is a lack of knowledge about the code, and that thorough review and testing is incompatible with the definition of vibe coding. Programmer Simon Willison said: "If an LLM wrote every line of your code, but you've reviewed, tested, and understood it all, that's not vibe coding in my book—that's using an LLM as a typing assistant." == Reception and use == In February 2025, New York Times journalist Kevin Roose, who is not a professional coder, experimented with vibe coding to create several small-scale applications. He described these as "software for one" due to the ability to personalize the software. However, Roose also stated that the results are often limited and prone to errors. In one case, the AI-generated code fabricated fake reviews for an e-commerce site. In response to Roose, cognitive scientist Gary Marcus said that the algorithm that generated Roose's LunchBox Buddy app had presumably been trained on existing code for similar tasks. Marcus said that Roose's enthusiasm stemmed from reproduction, not originality. In March 2025, Y Combinator reported that 25% of startup companies in its Winter 2025 batch had codebases that were 95% AI-generated, reflecting a shift toward AI-assisted development within newer startups. The question asked was about AI-generated code in general, and not specifically about vibed code. Inspired by "vibe coding", The Economist suggested the term "vibe valuation" to describe the very large valuations of AI startups by venture capital firms that ignore accepted metrics such as annual recurring revenue. In June 2025, Andrew Ng took issue with the term, saying that it misleads people into assuming that software engineers just "go with the vibes" when using AI tools to create applications. In July 2025, The Wall Street Journal reported that vibe coding was being adopted by professional software engineers for commercial use cases. In July 2025, SaaStr founder documented his negative experiences with vibe coding: Replit's AI agent deleted a database despite explicit instructions not to make any changes. In September 2025, Fast Company reported that the "vibe coding hangover" is upon us, with senior software engineers citing "development hell" when working with AI-generated code. It was reported in January 2026 that Linus Torvalds had made use of Google Antigravity to vibe code a tool component of his AudioNoise random digital audio effects generator. Torvalds explained in the project's README file that "the Python visualizer tool has been basically written by vibe-coding". == Criticism == === Quality of code and security issues === Vibe coding has raised concerns about understanding and accountability. Developers may use AI-generated code without comprehending its functionality, leading to undetected bugs, errors, or security vulnerabilities. While this approach may be suitable for prototyping or "throwaway weekend projects" as Karpathy originally envisioned, it is considered by some experts to pose risks in professional settings, where a deep understanding of the code is crucial for debugging, maintenance, and security. Ars Technica cites Simon Willison, who stated: "Vibe coding your way to a production codebase is clearly risky. Most of the work we do as software engineers involves evolving existing systems, where the quality and understandability of the underlying code is crucial." In May 2025, Lovable, a Swedish vibe coding app, was reported to have security vulnerabilities in the code it generated, with 170 out of 1,645 Lovable-created web applications having an issue that would allow personal information to be accessed by anyone. In October 2025 Veracode released a study that showed that over the last 3 years LLMs had become dramatically better at generating functional code, but that the security of generated code had generally not improved. Moreover, larger models were not better than small ones at generating secure code. There was a small increase in security from the OpenAI reasoning models, but not in other reasoning models, and this increase was nothing like the improvement in generated functionality. In December 2025, computer security researcher Etizaz Mohsin discovered a security flaw in the Orchids vibe coding platform, which he demonstrated to a BBC News reporter in February 2026. A December 2025 analysis by CodeRabbit of 470 open-source GitHub pull requests found that code that was co-authored by generative AI contained approximately 1.7 times more "major" issues compared to human-written code. The study revealed that AI co-authored code showed elevated rates of logic errors, including incorrect dependencies, flawed control flow, misconfigurations (75% more common), and security vulnerabilities (2.74x higher). Additionally, they also reported high code readability issues, including formatting errors and naming inconsistencies. === Code maintainability and technical debt === Vibe coding has the potential of making code harder to maintain in the longer term, leading to technical debt. In early 2025, GitClear published the results of a longitudinal analysis of 211 million lines of code changes from 2020 to 2024. They found that the volume of code refactoring dropped from 25% of changed lines in 2021 to under 10% by 2024, code duplication increased approximately four times in volume, copy-pasted code exceeded moved code for the first time in two decades, and code churn (prematurely merged code getting rewritten shortly after merging) nearly doubled. === Task complexity and developer productivity === Generative AI is highly capable of handling simple tasks like basic algorithms. However, such systems struggle with more novel, complex coding problems like projects involving multiple files, poorly documented libraries, or safety-critical code. In July 2025, METR, an organization that evaluates frontier models, ran a randomized controlled trial to understand developer productivity involving generative AI programming tools available in early 2025. They found that experienced open-source developers were 19% slower when using AI coding tools, despite predicting they would be 24% faster and still believing afterward they had been 20% faster. === Challenges with debugging === LLMs generate code dynamically, and the structure of such code may be subject to variation. In addition, since the developer did not write the code, the developer may struggle to understand its syntax and concepts. === Impact on open-source software === In January 2026, a paper authored by experts from several universities titled "Vibe Coding Kills Open Source" argued that vibe coding has negative impact on the open-source software ecosystem. The authors say that increased vibe coding reduces user engagement with open-source maintainers, which has hidden costs for said maintainers. Speaking with The Register about their paper, the authors argued:"Vibe coding raises productivity by lowering the cost of using and building on existing code, but it also weakens the user engagement through which many maintainers earn returns," the authors argue. "When OSS is monetized only through direct user engagement, greater adoption of vibe coding lowers e
Predicate (logic)
In logic, a predicate is a non-logical symbol that represents a property or a relation, though, formally, does not need to represent anything at all. For instance, in the first-order formula P ( a ) {\displaystyle P(a)} , the symbol P {\displaystyle P} is a predicate that applies to the individual constant a {\displaystyle a} which evaluates to either true or false. Similarly, in the formula R ( a , b ) {\displaystyle R(a,b)} , the symbol R {\displaystyle R} is a predicate that applies to the individual constants a {\displaystyle a} and b {\displaystyle b} . Predicates are considered a primitive notion of first-order, and higher-order logic and are therefore not defined in terms of other more basic concepts. The term derives from the grammatical term "predicate", meaning a word or phrase that represents a property or relation. In the semantics of logic, predicates are interpreted as relations. For instance, in a standard semantics for first-order logic, the formula R ( a , b ) {\displaystyle R(a,b)} would be true on an interpretation if the entities denoted by a {\displaystyle a} and b {\displaystyle b} stand in the relation denoted by R {\displaystyle R} . Since predicates are non-logical symbols, they can denote different relations depending on the interpretation given to them. While first-order logic only includes predicates that apply to individual objects, other logics may allow predicates that apply to collections of objects defined by other predicates. Strictly speaking, a predicate does not need to be given any interpretation, so long as its syntactic properties are well-defined. For example, equality may be understood solely through its reflexive and substitution properties (cf. Equality (mathematics) § Axioms). Other properties can be derived from these, and they are sufficient for proving theorems in mathematics. Similarly, set membership can be understood solely through the axioms of Zermelo–Fraenkel set theory. == Predicates in different systems == A predicate is a statement or mathematical assertion that contains variables, sometimes referred to as predicate variables, and may be true or false depending on those variables’ value or values. In propositional logic, atomic formulas are sometimes regarded as zero-place predicates. In a sense, these are nullary (i.e. 0-arity) predicates. In first-order logic, a predicate is a non-logical relation symbol, which forms an atomic formula when applied to an appropriate number of terms. In set theory with the law of excluded middle, predicates are understood to be characteristic functions or set indicator functions (i.e., functions from a set element to a truth value). Set-builder notation makes use of predicates to define sets. In autoepistemic logic, which rejects the law of excluded middle, predicates may be true, false, or simply unknown. In particular, a given collection of facts may be insufficient to determine the truth or falsehood of a predicate. In fuzzy logic, the strict true/false valuation of the predicate is replaced by a quantity interpreted as the degree of truth.
Collision detection
Collision detection is the computational problem of detecting an intersection of two or more objects in virtual space. More precisely, it deals with the questions of if, when, and where two or more objects intersect. Collision detection is a classic problem of computational geometry with applications in computer graphics, physical simulation, video games, robotics (including autonomous driving), and computational physics. Collision detection algorithms can be divided into operating on 2D or 3D spatial objects. == Overview == Collision detection is closely linked to calculating the distance between objects, as objects collide when the distance between them is less than or equal to zero. Negative distances indicate that one object has penetrated another. Performing collision detection requires more context than just the distance between the objects. Accurately identifying the points of contact on both objects' surfaces is also essential for computing a physically accurate collision response. The complexity of this task increases with the level of detail in the objects' representations: the more intricate the model, the greater the computational cost. Collision detection frequently involves dynamic objects, adding a temporal dimension to distance calculations. Instead of simply measuring distance between static objects, collision detection algorithms often aim to determine whether the objects' motion will bring them to a point in time when their distance is zero—an operation that adds significant computational overhead. In collision detection involving multiple objects, a naive approach would require detecting collisions for all pairwise combinations of objects. As the number of objects increases, the number of required comparisons grows rapidly: for n {\displaystyle n} objects, n ( n − 1 ) / 2 {n(n-1)}/{2} intersection tests are needed with a naive approach. This quadratic growth makes such an approach computationally expensive as n {\displaystyle n} increases. Due to the complexity mentioned above, collision detection is a computationally intensive process. Nevertheless, it is essential for interactive applications like video games, robotics, and real-time physics engines. To manage these computational demands, extensive efforts have gone into optimizing collision detection algorithms. A commonly used approach towards accelerating the required computations is to divide the process into two phases: the broad phase and the narrow phase. The broad phase aims to answer the question of whether objects might collide, using a conservative but efficient approach to rule out pairs that clearly do not intersect, thus avoiding unnecessary calculations. Objects that cannot be definitively separated in the broad phase are passed to the narrow phase. Here, more precise algorithms determine whether these objects actually intersect. If they do, the narrow phase often calculates the exact time and location of the intersection. == Broad phase == This phase aims at quickly finding objects or parts of objects for which it can be quickly determined that no further collision test is needed. A useful property of such approach is that it is output sensitive. In the context of collision detection this means that the time complexity of the collision detection is proportional to the number of objects that are close to each other. An early example of that is the I-COLLIDE where the number of required narrow phase collision tests was O ( n + m ) {\displaystyle O(n+m)} where n {\displaystyle n} is the number of objects and m {\displaystyle m} is the number of objects at close proximity. This is a significant improvement over the quadratic complexity of the naive approach. === Spatial partitioning === Several approaches can be grouped under the spatial partitioning umbrella, which includes octrees (for 3D), quadtrees (for 2D), binary space partitioning (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Dynamic scenes and deformable objects require updating the partitioning which can add overhead. === Bounding volume hierarchy === Bounding Volume Hierarchy (BVH) is a tree structure over a set of bounding volumes. Collision is determined by doing a tree traversal starting from the root. If the bounding volume of the root doesn't intersect with the object of interest, the traversal can be stopped. If, however there is an intersection, the traversal proceeds and checks the branches for each there is an intersection. Branches for which there is no intersection with the bounding volume can be culled from further intersection test. Therefore, multiple objects can be determined to not intersect at once. BVH can be used with deformable objects such as cloth or soft-bodies but the volume hierarchy has to be adjusted as the shape deforms. For deformable objects we need to be concerned about self-collisions or self intersections. BVH can be used for that end as well. Collision between two objects is computed by computing intersection between the bounding volumes of the root of the tree as there are collision we dive into the sub-trees that intersect. Exact collisions between the actual objects, or its parts (often triangles of a triangle mesh) need to be computed only between intersecting leaves. The same approach works for pair wise collision and self-collisions. === Exploiting temporal coherence === During the broad-phase, when the objects in the world move or deform, the data-structures used to cull collisions have to be updated. In cases where the changes between two frames or time-steps are small and the objects can be approximated well with axis-aligned bounding boxes, the sweep and prune algorithm can be a suitable approach. Several key observation make the implementation efficient: Two bounding-boxes intersect if, and only if, there is overlap along all three axes; overlap can be determined, for each axis separately, by sorting the intervals for all the boxes; and lastly, between two frames updates are typically small (making sorting algorithms optimized for almost-sorted lists suitable for this application). The algorithm keeps track of currently intersecting boxes, and as objects move, re-sorting the intervals helps keep track of the status. === Pairwise pruning === Once a pair of physical bodies has been selected for further investigation, collisions need to be checked more carefully. However, in many applications, individual objects (if they are not too deformable) are described by a set of smaller primitives, mainly triangles. So there are two sets of triangles, S = S 1 , S 2 , … , S n {\displaystyle S={S_{1},S_{2},\dots ,S_{n}}} and T = T 1 , T 2 , … , T n {\displaystyle T={T_{1},T_{2},\dots ,T_{n}}} (for simplicity, each set has the same number of triangles.) The obvious thing to do is to check all triangles S j {\displaystyle S_{j}} against all triangles T k {\displaystyle T_{k}} for collisions, but this involves n 2 {\displaystyle n^{2}} comparisons, which is highly inefficient. If possible, it is desirable to use a pruning algorithm to reduce the number of pairs of triangles that need to be checked. The most widely used family of algorithms is known as the hierarchical bounding volumes method. As a preprocessing step, for each object (e.g., S {\displaystyle S} and T {\displaystyle T} ) calculates a hierarchy of bounding volumes. Then, at each time step, when collisions need to be checked between S {\displaystyle S} and T {\displaystyle T} , the hierarchical bounding volumes are used to reduce the number of pairs of triangles under consideration. For simplicity, provide an example using bounding spheres, although it has been noted that spheres are undesirable in many cases. If E {\displaystyle E} is a set of triangles, a bounding sphere is pre-calculated. B ( E ) {\displaystyle B(E)} . There are many ways of choosing B ( E ) {\displaystyle B(E)} , B ( E ) {\displaystyle B(E)} is a sphere that completely contains E {\displaystyle E} and is as small as possible. Ahead of time, B ( S ) {\displaystyle B(S)} and B ( T ) {\displaystyle B(T)} can be computed. Clearly, if these two spheres do not intersect (and that is very easy to test), then neither do S {\displaystyle S} and T {\displaystyle T} . This is not much better than an n-body pruning algorithm, however. If E = E 1 , E 2 , … , E m {\displaystyle E={E_{1},E_{2},\dots ,E_{m}}} is a set of triangles, then split it into two halves L ( E ) := E 1 , E 2 , … , E m / 2 {\displaystyle L(E):={E_{1},E_{2},\dots ,E_{m/2}}} and R ( E ) := E m / 2 + 1 , … , E m − 1 , E m {\displaystyle R(E):={E_{m/2+1},\dots ,E_{m-1},E_{m}}} . Apply this to S {\displaystyle S} and T {\displaystyle T} , and calculate (ahead of time) the bounding spheres B ( L ( S ) ) , B ( R ( S ) ) {\displaystyle B(L(S)),B(R(S))} and B ( L ( T ) ) , B ( R ( T ) ) {\displaystyle B(L(T)),B(R(T))} . T
Agent mining
Agent mining is a research field that combines two areas of computer science: multiagent systems and data mining. It explores how intelligent computer agents can work together to discover, analyze, and learn from large amounts of data more effectively than traditional methods. == Historical context == The interaction and the integration between multiagent systems and data mining have a long history. The very early work on agent mining focused on agent-based knowledge discovery, agent-based distributed data mining, and agent-based distributed machine learning, and using data mining to enhance agent intelligence. The International Workshop on Agents and Data Mining Interaction has been held for more than 10 times, co-located with the International Conference on Autonomous Agents and Multi-Agent Systems. Several proceedings are available from Springer Lecture Notes in Computer Science.