Published on Tue Aug 14 2007

Solving the subset-sum problem with a light-based device

Mihai Oltean, Oana Muntean

The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. The nodes are connected by arcs in a special way which lets us toGenerate all possible subsets of the given set.

0
0
0
Abstract

We propose a special computational device which uses light rays for solving the subset-sum problem. The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. The nodes are connected by arcs in a special way which lets us to generate all possible subsets of the given set. To each arc we assign either a number from the given set or a predefined constant. When the light is passing through an arc it is delayed by the amount of time indicated by the number placed in that arc. At the destination node we will check if there is a ray whose total delay is equal to the target value of the subset sum problem (plus some constants).

Sun Mar 24 2019
Computer Vision
PLMP -- Point-Line Minimal Problems in Complete Multi-View Visibility
We present a complete classification of all minimal problems for generic arrangements of points and lines. We show that there are only 30 minimal problems in total, no problems exist for more than 6 cameras. We present a sequence of tests for detecting minimality starting with counting degrees of freedom.
0
0
0
Fri Mar 08 2019
Computer Vision
Geometry-Aware Graph Transforms for Light Field Compact Representation
The paper addresses the problem of energy compaction of dense 4D light fields. Local graphs are constructed on super-rays that can be seen as a grouping of spatially and geometry-dependent angularly correlated pixels.
0
0
0
Sun Jan 15 2017
Computer Vision
Light Source Estimation with Analytical Path-tracing
We present a novel algorithm for light source estimation in scenesreconstructed with a RGB-D camera based on an analytically-derived formulation of path-tracing. Our algorithm traces the reconstructed scene with a custom path-tracer and computes the analytical derivatives from principles in optics.
0
0
0
Thu Jul 09 2009
Computer Vision
Augmenting Light Field to model Wave Optics effects
The ray-based 4D light field representation cannot be directly used to analyze diffractive or phase--sensitive optical elements. We introduce a key modification to the model to support the transform. We insert a "virtual light source" with potentially negative valued radiance for certain emitted rays.
0
0
0
Fri Jun 09 2017
Artificial Intelligence
A Focal Any-Angle Path-finding Algorithm Based on A* on Visibility Graphs
The algorithm proposed is demonstrated on various path-finding cases. The performance of the new technique on visibility graphs is compared to the traditional A* on Grids, Theta* and A* On Visibility Graphs.
0
0
0
Thu Nov 07 2019
Machine Learning
Linear Constrained Rayleigh Quotient Optimization: Theory and Algorithms
Lanczos algorithm is used to solve constrained Rayleigh quotient optimization problems. The Lanczos algorithm can be applied to semi-supervised learning in the context of constrained clustering. The method is based on the Krylov subspace projection method.
0
0
0