About the Book

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

• By Language
  • C
  • C++
  • C#
  • Java
  • FORTRAN
  • Python
  • Mathematica
  • Pascal
  • ADA
  • Lisp
  • Binary
• By Problem
  • 1.1 Data Structures
    • Dictionaries
    • Priority Queues
    • Suffix Trees and Arrays
    • Graph Data Structures
    • Set Data Structures
    • Kd-Trees
  • 1.2 Numerical Problems
    • Solving Linear Equations
    • Bandwidth Reduction
    • Matrix Multiplication
    • Determinants and Permanents
    • Constrained and Unconstrained Optimization
    • Linear Programming
    • Random Number Generation
    • Factoring and Primality Testing
    • Arbitrary Precision Arithmetic
    • Knapsack Problem
    • Discrete Fourier Transform
  • 1.3 Combinatorial Problems
    • Sorting
    • Searching
    • Median and Selection
    • Generating Permutations
    • Generating Subsets
    • Generating Partitions
    • Generating Graphs
    • Calendrical Calculations
    • Job Scheduling
    • Satisfiability
  • 1.4 Graph Problems -- polynomial-time problems
    • Connected Components
    • Topological Sorting
    • Minimum Spanning Tree
    • Shortest Path
    • Transitive Closure and Reduction
    • Matching
    • Eulerian Cycle / Chinese Postman
    • Edge and Vertex Connectivity
    • Network Flow
    • Drawing Graphs Nicely
    • Drawing Trees
    • Planarity Detection and Embedding
  • 1.5 Graph Problems -- hard problems
    • Clique
    • Independent Set
    • Vertex Cover
    • Traveling Salesman Problem
    • Hamiltonian Cycle
    • Graph Partition
    • Vertex Coloring
    • Edge Coloring
    • Graph Isomorphism
    • Steiner Tree
    • Feedback Edge/Vertex Set
  • 1.6 Computational Geometry
    • Robust Geometric Primitives
    • Convex Hull
    • Triangulation
    • Voronoi Diagrams
    • Nearest Neighbor Search
    • Range Search
    • Point Location
    • Intersection Detection
    • Bin Packing
    • Medial-Axis Transformation
    • Polygon Partitioning
    • Simplifying Polygons
    • Shape Similarity
    • Motion Planning
    • Maintaining Line Arrangements
    • Minkowski Sum
  • 1.7 Set and String Problems
    • Set Cover
    • Set Packing
    • String Matching
    • Approximate String Matching
    • Text Compression
    • Cryptography
    • Finite State Machine Minimization
    • Longest Common Substring
    • Shortest Common Superstring
• Algorithm Links
  • Algorithm Lectures
  • Algorithm Design Manual Information
  • CSE 373 Course page
  • NIST Dictory of Algorithms and Data Structures
  • World of Mathematics
  • Programming Challenges
  • Graduate Study Opportuinties

A Library for interface detection of three-dimensional polygonal objects undergoing rigid motion

SOLID is a library for collision detection of three-dimensional objects undergoing rigid motion and deformation. SOLID is designed to be used in interactive 3D graphics applications, and is especially suited for collision detection of objects and worlds described in VRML. Some of the features are:

• Object shapes are represented by primitive shapes (box, cone, cylinder, sphere), and complexes of polytopes (line segments, convex polygons, convex polyhedra). A single shape can be used to instantiate multiple objects.
  
  
• Motion is specified by translations, rotations, and nonuniform scalings of the local  coordinate system of each moving object. These changes can be given absolute or relative to the previous frame. The local coordinate system can also be set according to an array of sixteen floats or doubles representing a 4x4 column-major matrix of an affine transformation, as used in OpenGL.
  
  
• Deformations of complex shapes can be specified using client-defined vertex arrays.
  
  
• Caollision response is defined by the client by means of call-back functions. Response may be defined per object pair, for all pairs containing a specific object, and as default for all pairs of objects.
  
  
• Response call-backs can use collision data describing the configuration of a pair of colliding objects. As collision data can be used a point common to both objects, and the closest point pair of the objects from the previous frame. The latter response type can be used for approximating the collision plane in physics-based simulations.
  
  
• Frame coherence is exploited by maintaining a set of pairs of proximate objects (incremental sweep and prune of axis-aligned bounding boxes), and caching separating axes for these pairs.  This feature is optional and may be turned on/off at any time during a simulation.