If you made any changes in Pure these will be visible here soon.

Research Output 2008 2019

2019

Algorithmic approaches to reconfigurable assembly systems

Costa, A., Abdel-Rahman, A., Jenett, B., Gershenfeld, N., Kostitsyna, I. & Cheung, K., 6 Dec 2019, 2019 IEEE Aerospace Conference, AERO 2019. Piscataway: Institute of Electrical and Electronics Engineers, 8 p. 8741572

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

robotics
Robotics
assembly
fault tolerance
structural design
1 Citation (Scopus)

Approximating (k,ℓ)-center clustering for curves

Buchin, K., Driemel, A., Gudmundsson, J., Horton, M., Kostitsyna, I., Löffler, M. & Struijs, M., 2 Jan 2019, 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Chan, T. M. (ed.). Society for Industrial and Applied Mathematics (SIAM), p. 2922-2938 17 p.

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Open Access
Clustering
Curve
Simplification
Approximation
Hardness of Approximation

Folding polyominoes with holes into a cube

Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M. L., Fekete, S. P., Kleist, L., Kostitsyna, I., Löffler, M., Masárová, Z., Mundilova, K. & Schmidt, C., 1 Jan 2019, Proceedings of the 31th Annual Canadian Conference on Computational Geometry CCCG 2019. p. 164-170 7 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Polyominoes
Folding
Polyomino
Regular hexahedron
Unit cube

Most vital segment barriers

Kostitsyna, I., Löffler, M., Polishchuk, V. & Staals, F., 12 Jul 2019, Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings. Friggstad, Z., Salavatipour, M. R. & Sack, J-R. (eds.). Cham: Springer, p. 495-509 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11646 LNCS)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Hardness
Path
Network Flow
Arc of a curve
Efficient Algorithms

Preprocessing ambiguous imprecise points

Hoog, I. V. D., Kostitsyna, I., Löffler, M. & Speckmann, B., 1 Jun 2019, 35th International Symposium on Computational Geometry (SoCG 2019). Barequet, G. & Wang, Y. (eds.). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Vol. 129, p. 42:1-42:16 16 p. 42. (Leibniz International Proceedings in Informatics (LIPIcs))

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Ambiguous
Preprocessing
Entropy
Sorting
Overlap

Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

Buchin, K., Kostitsyna, I., Löffler, M. & Silveira, R. I., 1 Jul 2019, In : Algorithmica. 81, 7, p. 2682–2715

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Visibility
Probability distributions
Probability density function
Probability Distribution
Polygon
2018

An optimal algorithm to compute the inverse beacon attraction region

Kostitsyna, I., Kouhestani, B., Langerman, S. & Rappaport, D., 2018, Proc. 34th International Symposium on Computational Geometry (SoCG). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 55:1-55:14 (Leibniz International Proceedings in Informatics (LIPIcs); vol. 99)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
Trees (mathematics)
Robotics
Trajectories

An optimal algorithm to compute the inverse beacon attraction region

Kostitsyna, I., Kouhestani, B., Langerman, S. & Rappaport, D., 15 Mar 2018, In : arXiv. 14 p., 1803.05946v1

Research output: Contribution to journalArticleAcademic

Open Access
File
Trees (mathematics)
Robotics
Trajectories

Approximating $(k,\ell)$-center clustering for curves

Buchin, K., Driemel, A., Gudmundsson, J., Horton, M., Kostitsyna, I., Löffler, M. & Struijs, M., 3 May 2018, In : arXiv. 24 p., 1805.01547v2

Research output: Contribution to journalArticleAcademic

Open Access
File
Clustering
Curve
Center Problem
Simplification
Approximation

Computing nonsimple polygons of minimum perimeter

Fekete, S. P., Haas, A., Hemmer, M., Hoffmann, M., Kostitsyna, I., Krupke, D., Maurer, F., Mitchell, J. S. B., Schmidt, A., Schmidt, C. & Troegel, J., 2018, In : Journal of Computational Geometry. 8, 1, p. 340-365 26 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Perimeter
Travelling salesman problems
Polygon
Computing
Curve Reconstruction

Convex hull formation for programmable matter

Daymude, J. J., Gmyr, R., Hinnenthal, K., Kostitsyna, I., Scheideler, C. & Richa, A. W., 16 May 2018, In : arXiv. 25 p., 1805.06149v1

Research output: Contribution to journalArticleAcademic

Open Access
File
Seals

Convex partial transversals of planar regions

Keikha, V., van de Kerkhof, M., van Kreveld, M., Kostitsyna, I., Löffler, M., Staals, F., Urhausen, J., Vermeulen, J. L. & Wiratma, L., 1 Dec 2018, 29th International Symposium on Algorithms and Computation, ISAAC 2018. Lee, D-T., Liao, C-S. & Hsu, W-L. (eds.). Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 12 p. 52. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 123)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Computational complexity
Polynomials
Testing

Convex partial transversals of planar regions

Keikha, V., Kerkhof, M. V. D., Kreveld, M. V., Kostitsyna, I., Löffler, M., Staals, F., Urhausen, J., Vermeulen, J. L. & Wiratma, L., 26 Sep 2018, In : arXiv. 29 p., 1809.10078v1

Research output: Contribution to journalArticleAcademic

Transversals
Partial
Line segment
Disjoint
Intersect

Forming tile shapes with simple robots

Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C. & Strothmann, T., 2018

Research output: Contribution to conferenceAbstractAcademic

File
Tile
Robots
Finite automata

Forming tile shapes with simple robots

Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C. & Strothmann, T., 2018, DNA Computing and Molecular Programming. Doty, D. & Dietz, H. (eds.). Cham: Springer, p. 122-138 17 p. (Lecture Notes in Computer Science; vol. 1145)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Tile
Robots
Finite automata

On optimal min-# curve simplification problem

Kerkhof, M. V. D., Kostitsyna, I., Löffler, M., Mirzanezhad, M. & Wenk, C., 26 Sep 2018, In : arXiv. 24 p., 1809.10269v1

Research output: Contribution to journalArticleAcademic

Open Access
File
Simplification
Curve
NP-hardness
Hausdorff Distance
Distance Measure

Shape recognition by a finite automaton robot

Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D. & Scheideler, C., 2018, p. 73:1-73:6 6 p.

Research output: Contribution to conferenceAbstractAcademic

Open Access
File
Finite automata
Robots
Tile
Exponential functions
Polynomials
2 Citations (Scopus)

Shape recognition by a finite automaton robot

Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D. & Scheideler, C., 2018, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS). Potapov, I., Spirakis, P. & Worrell, J. (eds.). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 52:1-52:15 15 p. 52. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 117)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Finite automata
Robots
Tile
Exponential functions
Polynomials

The hardness of Witness puzzles

Kostitsyna, I., Löffler, M., Sondag, M. F. M., Sonke, W. M. & Wulms, J. J. H. M., 2018, p. 67:1-67:6 6 p.

Research output: Contribution to conferenceAbstractAcademic

Open Access
File

Theoretical analysis of beaconless geocast protocols in 1D

Gudmundssons, J., Kostitsyna, I., Löffler, M., Müller, T., Sacristán, V. & Silveira, R. I., 2018, Proc. 15th Workshop on Analytic Algorithmics and Combinatorics (ANALCO). p. 62-76 15 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Network protocols
Wireless ad hoc networks
Routing protocols
Computer simulation
1 Citation (Scopus)

The painter’s problem: Covering a grid with colored connected polygons

van Goethem, A. I., Kostitsyna, I., van Kreveld, M. J., Meulemans, W., Sondag, M. F. M. & Wulms, J. J. H. M., 2018, 25th International Symposium on Graph Drawing and Network Visualization (GD): Revised Selected Papers. Frati, F. & Ma, K-L. (eds.). Cham: Springer, Vol. 10692 LNCS, p. 492-505 14 p. (Lecture Notes in Computer Science; vol. 10692)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Covering Problem
Painting
Polygon
Color
Grid

Towards hybrid programmable matter : shape recognition, formation, and sealing algorithms for finite automaton robots

Daymunde, J., Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Richa, A., Rudolph, D., Scheideler, C. & Strothmann, T., 2018

Research output: Contribution to conferencePosterAcademic

Open Access
File
2017

Forming tile shapes with a single robot

Gmyr, R., Kostitsyna, I., Kuhn, F., Scheideler, C. & Strothmann, T., 2017, p. 9-12 4 p.

Research output: Contribution to conferenceAbstractAcademic

Open Access
File

Non-crossing drawings of multiple geometric Steiner arborescences

Kostitsyna, I., Speckmann, B. & Verbeek, K. A. B., 2017, p. 133-136 4 p.

Research output: Contribution to conferenceAbstractAcademic

Open Access
File

Non-crossing geometric steiner arborescences

Kostitsyna, I., Speckmann, B. & Verbeek, K. A. B., 2017, Proc. 28th International Symposium on Algorithms and Computation (ISAAC). Okamoto, Y. & Tokuyama, T. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-13 54. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 92)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Roots
Steiner Point
Angle
Path
NP-hardness

On the complexity of minimum-link path problems

Kostitsyna, I., Löffler, M., Polishchuk, V. & Staals, F., 2017, In : Journal of Computational Geometry. 8, 2, p. 80-108 29 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Ray tracing
Computer graphics
Telecommunication links
Computational complexity
Hardness
1 Citation (Scopus)

Self-approaching paths in simple polygons

Bose, P., Kostitsyna, I. & Langerman, S., 2017, Proc. 33rd International Symposium on Computational Geometry (SoCG). p. 1-15 15 p. 21. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 77)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Simple Polygon
Path
Polygon
Curve
Models of Computation

Self-approaching paths in simple polygons

Bose, P., Kostitsyna, I. & Langerman, S., 2017, p. 13-16 4 p.

Research output: Contribution to conferenceAbstractAcademic

Open Access
File

The Painter's Problem: covering a grid with colored connected polygons

van Goethem, A. I., Kostitsyna, I., van Kreveld, M., Meulemans, W., Sondag, M. F. M. & Wulms, J. J. H. M., 30 Sep 2017, In : arXiv. 1709.00001, 20 p., 1709.00001

Research output: Contribution to journalArticleAcademic

Open Access
File
Covering Problem
Polygon
Grid
Cell
Hypergraph
1 Citation (Scopus)

Unfolding and dissection of multiple cubes, tetrahedra, and doubly covered squares

Abel, Z., Ballinger, B., Demaine, E. D., Demaine, M. L., Erickson, J., Hesterberg, A., Ito, H., Kostitsyna, I., Lynch, J. & Uehara, R., 2017, In : Journal of Information Processing. 25, p. 610-615 6 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Dissection
Tile
2016

Beaconless geocast protocols are interesting, even in 1D

Gudmundsson, J., Kostitsyna, I., Löffler, M., Sacristán, V. & Silveira, R., 2016, p. 227-230

Research output: Contribution to conferenceAbstractAcademic

Open Access
File
1 Citation (Scopus)

Computing nonsimple polygons of minimum perimeter

Fekete, S. P., Haas, A., Hemmer, M., Hoffmann, M., Kostitsyna, I., Krupke, D., Maurer, F., Mitchell, J. S. B., Schmidt, A., Schmidt, C. & Troegel, J., 2016, Proc. 15th International Symposium on Experimental Algorithms (SEA). Goldberg, A. V. & Kulikov, A. S. (eds.). Dordrecht: Springer, p. 134-149 16 p. (Lecture Notes in Computer Science; vol. 9685)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Perimeter
Polygon
Computing
Curve Reconstruction
Cycle Cover

Critical placements of a square or circle amidst trajectories for junction detection

van Duijn, I., Kostitsyna, I., van Kreveld, M. J. & Löffler, M., 2016, Proceedings of the28th Canadian Conference on Computational Geometry : August 3-5, 2016, Simon Fraser University, Vancouver, British Columbia, Canada. p. 208-215 8 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
7 Citations (Scopus)

Gabriel triangulations and angle-monotone graphs : local routing and recognition

Bonichon, N., Bose, P., Carmi, P., Kostitsyna, I., Lubiw, A. & Verdonschot, S., 2016, Graph Drawing and Network Visualization : 24th International Symposium., GD 2016, Athens, Greece, September 19-21, 2046. Revised Selected Papers. Hu, Y. & Nöllenburg, M. (eds.). Dordrecht: Springer, p. 519-531 13 p. (Lecture Notes in Computer Science; vol. 9801)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Triangulation
Monotone
Routing
Angle
Graph in graph theory

Homotopy measures for representative trajectories

Chambers, E. W., Kostitsyna, I., Löffler, M. & Staals, F., 2016, Proc. 24th Annual European Symposium on Algorithms (ESA). p. 1-17 27. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 57)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Trajectories
Geometry

Mapping polygons to the grid with small Hausdorff and Fréchet distance

Bouts, Q. W., Kostitsyna, I., van Kreveld, M. J., Meulemans, W., Sonke, W. & Verbeek, K. A. B., 21 Jun 2016, In : arXiv. 33 p.

Research output: Contribution to journalArticleAcademic

Open Access
File
Pixels
Experiments
3 Citations (Scopus)

Mapping polygons to the grid with small Hausdorff and Fréchet distance

Bouts, Q. W., Kostitsyna, I., van Kreveld, M. J., Meulemans, W., Sonke, W. M. & Verbeek, K. A. B., 1 Aug 2016, Proc. 24th Annual European Symposium on Algorithms (ESA). Sankowski, P. & Zaroliagis, C. (eds.). s.l.: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-16 22. (Leibniz International Proceedings in Informatics; vol. 57)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Pixels
Experiments

Mapping polygons to the grid with small Hausdorff and Fréchet distance

Bouts, Q. W., Kostitsyna, I., van Kreveld, M. J., Meulemans, W., Sonke, W. M. & Verbeek, K. A. B., 1 Apr 2016, p. 247-250 4 p.

Research output: Contribution to conferenceAbstractAcademic

Open Access
File
Pixels
Experiments
2 Citations (Scopus)

On the complexity of minimum-link path problems

Kostitsyna, I., Löffler, M., Polishchuk, V. & Staals, F., 2016, Proc. 32nd International Symposium on Computational Geometry (SoCG). Fekete, S. & Lubiw, A. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-16 16 p. 49. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 51)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Open Problems
Path
Resolve
NP-complete problem
FPTAS
3 Citations (Scopus)

Single-player and two-player buttons & scissors games (extended abstract)

Burke, K., Demaine, E. D., Gregg, H., Hearn, R. A., Hesterberg, A., Hoffmann, M. H. W., Ito, H., Kostitsyna, I., Leonard, J., Löffler, M., Santiago, A., Schmidt, C., Uehara, R., Uno, Y. & Williams, A., 2016, Discrete and Computational Geometry and Graphs : 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015 : Revised Selected Papers. Akiyama, J., Ito, H., Sakai, T. & Uno, Y. (eds.). Dordrecht: Springer, p. 60-72 13 p. ( Lecture Notes in Computer Science; vol. 9943)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Color
Computational complexity

Unfolding and dissection of multiple cubes

Abel, Z., Ballinger, B., Demaine, E. D., Demaine, M. L., Erickson, J., Hesterberg, A., Ito, H., Kostitsyna, I., Lynch, J. & Uehara, R., 2016, Abstracts of the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Dissection
Unfolding
Regular hexahedron
Polyomino
Polyominoes
2015
1 Citation (Scopus)

Folding polyominoes into (poly)cubes

Aichholzer, O., Biro, M., Demaine, E. D., Demaine, M. L., Eppstein, D., Fekete, S. P., Hesterberg, A., Kostitsyna, I. & Schmidt, C., 2015, Proc. 27th Canadian Conference on Computational Geometry (CCCG). p. 1-6 37

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File

Homotopy measures for representative trajectories

Chambers, E. W., Kostitsyna, I., Löffler, M. & Staals, F., 2015

Research output: Contribution to conferenceAbstractAcademic

Open Access
File
2 Citations (Scopus)

On minimizing crossings in storyline visualizations

Kostitsyna, I., Nöllenburg, M., Polishchuk, V., Schulz, A. & Strash, D., 2015, s.n.(arXiv; vol. 1509.00442)

Research output: Book/ReportReportAcademic

Visualization
6 Citations (Scopus)

On minimizing crossings in storyline visualizations

Kostitsyna, I., Nöllenburg, M., Polishchuk, V., Schulz, A. & Strash, D., 2015, Proc. 23rd International Symposium Graph Drawing and Network Visualization (GD). Di Giacomo, E. & Lubiw, A. (eds.). Dordrecht: Springer, p. 192-198 7 p. (Lecture Notes in Computer Science; vol. 9411)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Visualization
Diverge
Upper and Lower Bounds
Monotone
Converge
1 Citation (Scopus)

Optimizing airspace closure with respect to politicians’ egos

Kostitsyna, I., Löffler, M. & Polishchuk, V., 2015, In : Theoretical Computer Science. 586, p. 161-175

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Airports
Data structures
Data Structures
Closure
Traffic
2 Citations (Scopus)

Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

Buchin, K., Kostitsyna, I., Löffler, M. & Silveira, R. I., 2015, Proc. 17th Workshop on Algorithm Engineering and Experiments (ALENEX). Brandes, U. & Eppstein, D. (eds.). Philadelphia: Society for Industrial and Applied Mathematics (SIAM), p. 94-103

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Visibility
Probability distributions
Experiments
5 Citations (Scopus)

Trajectory grouping structure under geodesic distance

Kostitsyna, I., van Kreveld, M. J., Löffler, M., Speckmann, B. & Staals, F., 1 Jun 2015, Proc. 31st International Symposium on Computational Geometry (SoCG). s.l.: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 674-688 15 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
Trajectories
2014
1 Citation (Scopus)

Optimizing airspace closure with respect to politicians’ egos

Kostitsyna, I., Löffler, M. & Polishchuk, V., 2014, Proc. 7th International Conference on Fun with Algorithms (FUN). Ferro, A., Luccio, F. & Widmayer, P. (eds.). Berlin: Springer, p. 264-276 (Lecture Notes in Computer Science; vol. 8496)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Airports
Landing
Data structures
Aircraft

Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

Buchin, K., Kostitsyna, I., Löffler, M. & Silveira, R. I., 2014, Abstr. 30th European Workshop on Computational Geometry (EuroCG). p. 1-4

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Visibility
Probability density function
Probability Distribution
Computational Geometry
Approximation