During my bachelor's I got interested in Computational Geometry (CG).
Computational Geometry is algorithms over geometric graphs; a geometric graph is a graph where the vertices are points on the plane (space) and the edges are (curve) straight line segments.
What I like the most about CG is its visual nature.
Graphs admit any possible depiction that you wish, but geometric graphs only admit "one".
After I joined a research group in CG, I decided to create a program to work with geometric graphs.
Specially because I wanted to be able to write an algorithm prototype fast and "see" the result of its execution.
Relating it to Software Engineering I wanted to write an algorithm and have a "test suite", a set of graphs, to test the algorithm and see the execution.
At the time I was aware of CGAL (The Computational Geometry Algorithms Library).
CGAL's focus is precision and performance but it lacked of a GUI interface and the learning curve was (is?) steep.
Unless you are already a CGAL expert, fast prototyping would be difficult.
My intended type of user was someone who is familiar with geometric graphs and just want to run an algorithm to study the result, to debug it.
So, the precision guarantees offered by CGAL at the expense of the learning curve was not appealing to me.
In my mind, the software I wanted would be used for exploring ideas and once an idea is polished then it could be moved over to CGAL for performance.
In short the software I wanted must fulfill the following goals:
1. Create graphs with mouse and keyboard and programmatically.
2. Run algorithms on the created graphs.
3. Allow fast development of algorithm ideas.
4. NO third-party libraries.
The next decision was the programming language.
I chose Objective-C because I wanted to try (native) GUI development for Mac OS X; at the time Objective-C was a new language to me.
I think it has a wonderful syntax compared to other languages like C, C++, Java, etc.
For example [graph addVertex:x andY:y] or [graph addEdgeFrom:a to:b] seems to me quite elegant and
to the point.
The result was CGR which stands for Computational Geometry Rover.
Under the hood, every vertex and edge is an Objective-C object with properties that can be modified like the radius and color of vertices.
The API exposed the objects of the elements as well as their identifiers.
So, it was possible to, for example, add an edge using the objects of the vertices or only their identifiers (natural numbers).
To display the graph, I used Cocoa's capabilities like NSBezierPath.
I was quite happy with CGR, I enjoyed the pleasant look-and-feel of the graphs.
I also used it to find the average number of Steiner points in my bachelor's thesis topic: Triangulations of Minimal Chromatic Number.
During my master's my interested focused on CG and Wireless (Sensor) Networks (WSN), in particular its application on Topology Control (TC).
Topology Control are the techniques used to keep a WSN connected to fulfill a metric, for example, to keep the network resilient to node failure or with the best quality of service possible.
CG was among the first tools to model WSN and a plethora of papers were published on TC following those models.
WSN and TC were a natural application for CGR, however, CGR had several short-comings.
It was single-threaded, that means, the evolution of a TC algorithm could not be seen "live"; only the end result.
It was 'memory-hungry'; even if you want to only toy with an idea, you would require hundreds of nodes, and at that time CGR consumed almost all of my MacBook's memory with only 700 (or so) nodes, just for displaying purposes.
It was clear that I needed to 'upgrade' CGR if I wanted to simulate WSNs with it.
However, instead of 'upgrading it' I rewrote it from scratch.
I also added new goals to this new version to help me model WSNs:
5. The graphs should support edge parallelism.
6. Should be able to depict the evolution of a programmed algorithm.
7. Support for graph properties that algorithms can load on-demand.
8. Support for graph constraints that algorithms can load on-demand.
9. Support for sub-graphs.
10. Support for distributed viewer, a graph is hosted in one computer and is displayed on another.
The result was CGRMTFramework, and CGRMT.
The MT stands for Multi-Threaded.
CGR was divided in two, a framework/library (CGRMTFramework) and a GUI (CGRMT) because it adopts the model-view-controller pattern.
One of the heaviest burdens of CGR was the use of Cocoa's primitives to draw the objects on the screen.
In CGRMT I decided to learn and use OpenGL to draw the graphs.
CGRMTFramework is quite decent, it is not as memory hungry as CGR considering the vertices and edges are still Objective-C objects and it is also decently fast.
CGRMT, the GUI, is also nice, the graphs are still pleasant to look at.
The overall idea for simulating WSNs with CGRMTFramework was to have a property tracking each vertex (sensor) and its neighborhood to determine which nodes it can talk to.
Every time a link is created, it would be recorded so it could be played back later to watch the simulation unfold.
Nodes can also have constraints assigned to them to model link selection and so on.
However, it was evident almost as soon as I started implementing CGRMTFramework that simulating wireless networks using a "naked" multi-core approach, was a bad idea because the results would not be reproducible.
The simulations might look nice, the kind you would see in a movie, which is what I was after, but the results would be challenging to reproduce.
Nevertheless I didn't abandon the idea of supporting parallelism at the edge level, as it might be helpful for other types of algorithms.
CGRMTFramework and CGRMT delivered and I simulated a good amount of networks and topology control algorithms.
By that time I toyed with the idea of having a true decentralized wireless network made of cellphones, my wildest fantasy was intercontinental messaging.
Suppose I want to send an SMS to a friend in Europe, say, Germany.
I live in Mexico City so I send the SMS to the network, the SMS finds its way into a cellphone of a passenger of a plane to Madrid.
Once the passenger reaches Madrid the SMS finds its way into another passenger of another plane heading to Frankfurt and from there jumping around local cellphone and finally to my friend.
This would require being able to simulate networks on the million nodes, obviously.
The network would be flooded with messages from all over the place and probably would drain the batteries of the phones.
But I think it was a nice idea, regardless.
A more realistic setting for this kind of networks is when a natural disaster hits an area.
If the cell towers are down, or the electricity is knocked out, the network would be alive and help to find people that needs help; cellphones are just fancy two-way radios with GPS.
Simulations offered a way to have a proof of concept without having to hack several cellphones and perform real-word tests.
However, the theoritical models (Unit Disk Graphs and Quasi-Unit Disk Graphs) are criticized because they are either too ideal or too pessimistic.
There were also models based on real-world deployments but those are specific for a certain environment, e.g. outdoors or office environments.
So, before designing a network, I had to solve the simulation problem.
And I wanted to solve it within CG without neglecting experimental results that contradict the model.
My solution was to unify all models by having nodes transmitting over "maps".
A map is a partition of the transmission area into sub-areas each with its own properties for propagating radio waves.
Then a node would start to transmit and its coverage would be modified with respect to the map.
With this approach I have consistency, if two identical nodes are at the same spot, both will have identical coverage areas, so the nodes could also move around the map.
To test this idea I selected a paper that reported connectivity of WSN in city-wide deployments and tried to generate maps to achieve similar connectivity.
The problem was: I needed big maps and once more, memory and speed began to be a problem once more.
I had to re-implement GCRMTFramework and CGRMT, but I didn't have much time to re-implement everything from scratch while keeping the visual aesthetics and the functionality of the GUI.
So I made the choice to focus on the mechanics and neglect the GUI.
That is how CGRCore came to be.
I changed the implementation language to Objective-C++ which is like having three languages in one: Objective-C, C and C++ (sort of).
I implemented all kinds of "weird" parallel and sequential containers that out-performed C++ standard library counterparts but I also kept using Foundation containers.
The idea was to have fun while keeping it "in-house", that is, without using 3rd-party libraries.
For the visual part, I decided to write an EPS file generator to make it easy to add figures to papers and presentations.
CGRMTFramework uses Metapost to draw graphs to pdf or eps.
This time I added new classes of graphs, I kept the original geometric graph but it was an specialization of a graph, and also introduced directed graphs and directed geometric graphs which would be needed to correctly simulate WSN; sometimes a node can hear another but it can not talk to it.
I also added new geometrical objects like polygons to have a lighter way to model transmission areas.
Not being completely happy, I also toyed with the idea of "lazy"/"on demand" graphs, which are graphs that are not completely present in memory but are calculated by parts.
With CGRCore I was able to simulate city-wide networks in decent time.
At some point I also implemented the OpenGL code necessary to display the graphs and various ad-hoc viewers.
I used it mostly to be able to debug simulation elements, but as far as I remember I didn't see any simulation unfold; unlike CGRMTFramework, CGRCore does not have "playback" (i.e. it is not implemented yet).
I stopped working on CGRCore around 2015 or so.
I never used CGRCore with graphs not made by myself.
I recently wanted to see if I could depict some projections of OFF files in the CGAL Git repository.
CGR does not have 3D geometric graphs, so I decided to draw the projections on the XY, YZ, and XZ planes of the graphs on the OFF files.
I didn't put too much effort on the OFF parser, so, there were a few files that didn't parse.
In total I could parse 135 files and each generated 3 independent graphs.
I also modified the viewer to display various graphs at the same time.
In total there were 405 independent graphs with 1.250.157 vertices and 3.641.217 edges.
CGRCore requires around 2.9 GB to display the graphs.
On the other hand a single random graph with the same dimensions takes around 930 MB to display the graphs.
These are 'full' graphs, the edges are capable of having data associated to them as well as the vertices, they are not optimized for mesh graphs.
I think the difference is due to two factors.
The first is the pre-allocation CGRCore performs for speed on the independent graphs.
The second is lazy edge containers initialization.
When a vertex is added, CGRCore only allocates the necessary memory to represent the vertex, and edge containers are initialized only when an edge incident in the vertex is added; the random graph has many single vertices as opposed to the OFFs graphs.
Here you can see CGRCore displaying the projections of the CGAL meshes.
Here you can see CGRCore displaying a random graph with 1.250.157 vertices and 3.641.217 edges.
Here you can see CGRMT reconstructing a graph and applying an even-odd property while the graph is being reconstructed.
A vertex is colored blue if it has even degree and red otherwise.
Here you can see CGRMT constructing a CGR Logo.
For a long time I wanted to include curves in CGR but I didn't have the time nor the problem domain.
Now, to construct the logo I decided to prototype a few curves to help me modify aspects of the logo without having to deal with a ton of equations and recompilations.
Each letter is created by points arranged along curves.
The points for a letter are first created randomly and then "pulled" to the curves and finally spread evenly over a sector of a curve.
Overall I think it is not so bad for a framework I haven't touch for more than 10 years on a computer almost 14 years old :)
Copyright Alfredo Cruz-Carlon, 2026