Finite Automata

Finite automata are good models for computers with an extremely limited amount of memory. The controller moves from state to state, depending on the input it receives. Finite automata and their probabilistic counterpart Markov Chains are useful tools when we are attempting to recognize patterns in data.

Formal Definition of a finite automaton

​ A finite automaton is a list of those five objects: set of states, input alphabet, rules for moving, start state, and accept states.

Definition... read more

Given a robot and set of obstacles, find the shortest path from $s$ to $t$ without collision.

Robot without collision volume

Starting from a point $s$ and finds a possible way to the end point $t$.

First, build a rectangle boundary and do the planar subdivision, pick the mid point for vertical planar edge and pick the mid point for ever face.

Find the shortest path from the face $f_s$ containing $s$ to that $f_t$ containing $t$. Add an... read more

A terrain is a 2-dimensional surface in 3-dimensional space with a special property: every vertical line intersects it in a point, if it intersects it at all. In other words, it is the graph of a function $f:A\subset \mathbb{R}^2\rightarrow\mathbb{R}$ that assigns a height $f(p)$ to every point $p$ in the domain, $A$, of the terrain.

Nevertheless, some triangulations look more natural than others. We will rank triangulations by comparing their smallest angle. Since there is only finite... read more

Problem: Given a set $S$ of $N$ points in the plane, for each point $p_i$ in $S$ what is the locus of points $(x,y)$ in the plane that are close to $p_i$ than to any other point $S$ ?

Definition locus is the set of points whose location satisfies by one or more specified conditions.

Given two points, $p_i$ and $p_j$, the set of points closer to $p_i$ than to $p_j$ is just the half-plane containing $p_i$ that is defined... read more

Point Location query Given a map and a query point $q$ specified by its coordinates, find the region of the map containing $q$. A map, of course, is nothing more than a subdivision of the plane into regions, a planar subdivision.

Idea To preprocess the maps and to store them in a data structure that makes it possible to answer point location queries fast.

Slab Method

Let $S$ be a planar subdivision with $n$ edges. The planar _... read more

Problem Given a set $S$ of $n$ closed segments in the plane, report all intersection points among the segments in $S$.

Theorem 2.4 Let $S$ be a set of $n$ line segments in the plane. All intersection points in $S$, with for each intersection point the segments involved in it, can be reported in $O(n\log n+I\log n)$ time and $O(n)$ space, where $I$ is the number of intersection points.

The double-Connected Edge List

Some Definition:

• A face... read more

Definition A query asking to report all records whose fields lie between specified values, then transforms to a query asking for all points inside a $d$-dimensional axis-parallel box. Such a query is called a rectangular range query, or an orthogonal range query in CG.

Normalization $x$- and $y$-coordinates of points can be replaced by integers $1,2,3,\cdots, n$ in $O(n\log n)$ time (First sort and re-index). When querying, the coordinates of of the rectangle corners... read more

Art gallery problem

Two points in a simple polygon can see each other if their connecting line segment is in the polygon.

Definition The art gallery problem:

​ How many points are needed in a simple polygon with $n$ vertices so that every point in the polygon is seen?

This problem is NP-hard.

Theorem art gallery theorem:

​ $\lfloor n/3\rfloor$ cameras are occasionally necessary but always sufficient.

Some Definition

• Polygon $P$ is triangulated: a decomposition of $P$ into disjoint triangles by... read more

Problem Definition

Given: A set $Z$ of $n$ points in the plane.

Find: Smallest convex set containing $Z$.

Some Basic Definition

1. A set $S$ in the plane is convex iff for every pair of points $p_1$ and $p_2$ in $S$, the line-segment $p_1p_2 $ is in $S$.
2. A point $p$ in a convex set $S$ is said to be extreme (or a corner) iff no segment $ab$ in $S$ has $p$ in its interior.
3. $CH(Z)$ is considered to be determined once... read more