Instance Files

In the context of this contest, an instances is a set of points in the Euclidean plane. These points have integer coordinates between -2⁴⁰ and 2⁴⁰, which implies that IEEE double precision floating point numbers can represent coordinates without loss of precision.

Our instances are available as a ZIP archive. For each instance, this archive contains a JSON (JavaScript Object Notation) file. The JSON format is a well-known, wide-spread format; there are JSON parser libraries for nearly all practically relevant programming languages. If you find integrating a JSON parser into your project too cumbersome, we provide a Python-based utility library containing an instance reader that you can use to transform the instance into a simpler format of your choice.

In this JSON format, an instance may look like this:

{
	"points": [
		{"i": 0, "x": -2396.0, "y": -5284.0},
		{"i": 1, "x": 2656.0, "y": 2938.0},
		{"i": 2, "x": 4120.0, "y": 2278.0},
		{"i": 3, "x": 4342.0, "y": 102.0},
		{"i": 4, "x": 4384.0, "y": 2988.0},
		{"i": 5, "x": 5136.0, "y": 2280.0},
		{"i": 6, "x": 6634.0, "y": 5416.0},
		{"i": 7, "x": 8598.0, "y": 2632.0},
		{"i": 8, "x": 8898.0, "y": 4170.0},
		{"i": 9, "x": 11738.0, "y": 1550.0}
	],
	"type": "Instance",
	"name": "example-0000010",
	"meta": {
		"comment": "HIP even point set instance (10 points) sampled from image",
		"faces_in_delaunay": 12
	}
}

Each instance JSON file contains exactly one object. That object contains at least a list of points called points, a name that is unique to the instance and an attribute type which is set to Instance, stating that this object actually encodes an instance. It may also contain a meta attribute, containing additional meta information, such as a comment, and the number of faces in a triangulation of the point set. Each entry in the list points is an object containing the three attributes i, x and y. x and y are the point's coordinates as IEEE double precision floating point values. i is the point index, an integer ranging from 0 to n-1, where n is the number of points in the instance. Each point is uniquely identified by its index. Moreover, there are no duplicate points in our instances; however, there are instances with collinear points, i.e., more than two points on a line.

Solution Files

In the context of this contest, a solution to an instance is a set of edges, i.e., pairs of vertex indices corresponding to the index i specified in the points list of the instance. The solution for an instance must satisfy the following conditions.

• No edge is a loop that connects a vertex to itself.
• Each vertex is incident to at least two edges.
• No edge intersects another edge in its interior.
• No point lies in the interior of an edge.
• The boundary of the convex hull of the points is covered (exactly) by a subset of output edges
• The finite faces of the arrangement induced by the edges are convex.

For this contest, you may upload your solutions as ZIP archives containing solutions files. Analogously to instance files, solutions are encoded in JSON; a solution may look as follows.

{
	"type": "Solution",
	"instance_name": "triangle-0000003",
	"meta": { "comment": "My Awesome Solver generated this solution!" },
	"edges": [
		{"i": 0, "j": 1},
		{"i": 1, "j": 2},
		{"i": 2, "j": 0}
	]
}

Similar to JSON parsers, there are JSON generators for virtually all practically relevant programming languages. If you generate solution files ad-hoc, remember that the attribute names in JSON, unlike in JavaScript, must be enclosed in quotation marks. A solution must have a type attribute set to Solution. Moreover, it must an attribute instance_name corresponding to the unique name given by the name attribute of the corresponding instance. Furthermore, the list of edges contained in the solution must be given as the edges attribute of the solution. Each edge is an object containing two attributes i and j indicating the indices of the points connected by the edge. Finally, a solution may contain a meta attribute containing metadata or a comment. Give the file the extension .solution.json.

Upload

Put all solution files into a zip. Our verifier will search all non-hidden folders for json files. Do not include any other files as it would bloat the zip and possibly confuse the verifier. We recommend to use our Python3 module cgshop2020_pyutils.