Regular Languages 8 minute read

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

Robot Motion 3 minute read

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

image-20210318143348856

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

Delaunay Triangulations 8 minute read

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.

image-20210317132256993

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

Voronoi Diagram 7 minute read

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 10 minute read

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

Line Segment Intersection 2 minute read

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:

Orthogonal Range Searching 7 minute read

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.

image-20210222172729789

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

Polygon Triangulation 4 minute read

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
Convex Hull 6 minute read

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